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
",res);
    }
    return 0;
}