10130 – SuperSale

A 0/1-Knapsack problem.
Apply the 0/1-Knapsack for each family member given the weight they can carry and sum the maximum up.
I added a little detail but it doesn’t make much of a difference. I sort the items according to their weights and start from light items until I reach an item I can’t add. Items heavier than that last item are, of course, no use so we return from there and stop the recursion.
C++ implementation:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1004
#define G 104
#define W 34
#define weight first
#define price second

int dp[N][W];
pair<int, int> item[N];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.weight > p2.weight;
}

int getMax(int n, int w) {
	if (n < 0)
		return 0;
	if (dp[n][w] != -1)
		return dp[n][w];
	if (w < item[n].weight)
		return dp[n][w] = 0;
	else
		return dp[n][w] = max(getMax(n - 1, w - item[n].weight) + item[n].price, getMax(n - 1, w));
}

int main() {
	int totT, totN, totG;
	cin >> totT;
	for (int i = 0; i < totT; ++i) {
		// input
		cin >> totN;
		for (int j = 0; j < totN; ++j)
			cin >> item[j].price >> item[j].weight;
		memset(dp, -1, sizeof dp);
		sort(item, item + totN, cmp);
		cin >> totG;
		// solve
		int sum = 0;
		for (int j = 0, w; j < totG; ++j) {
			cin >> w;
			sum += getMax(totN - 1, w);
		}
		cout << sum << endl;
	}
	return 0;
}