uva10130

题目大意：
超市大减价，全家一起去买东西，求能带回的价值最多是多少。
给出了几个人，和每个人可以承受的重量。

思路：
背包问题

代码：

#include <iostream>
using namespace std;
#include <cstring>
#include <stdio.h>
int MW[105];
int P[1005],W[1005];
int dp[40];
int main() {
    int T,N,G;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&N);
        for(int i = 1 ; i <= N; i++) {
            scanf("%d %d",&P[i],&W[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= N; i++) {
            for(int j = 30; j >= W[i];j--) {
                dp[j] = max(dp[j],dp[j - W[i]]+P[i]);
            }
        }
        scanf("%d",&G);
        int res = 0;
        int x;
        for(int i = 0 ; i < G; i++) {
            scanf("%d",&x);
            res += dp[x];
        }
        printf("%d\n",res);
    }
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：uva10130，转载请注明来源！