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; }