UVa 10130 SuperSale

題意：
    有一家超市有N種商品正在做特價，每種商品數量無限，但規定一個人每種只能買一個，P表示該種商品價值P元，W表示該種商品重W。現在有一家庭共G人，每個人都有不同的背包重量上限MW，問這一家人能買到最高商品價值為多少?

想法：
    背包問題，dp[MW]=k表示重量上限MW的背包裝的物品最多價值k。

	#include <cstdio>
	#include <algorithm>
	int T, N, G, MW;
	int price[1005], weight[1005];
	int dp[35];
	int Knapsack();
	int main()
	{
	scanf("%d", &T);
	while (T--) {
	// Input
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &price[i], &weight[i]);
	scanf("%d", &G);
	std::fill(std::begin(dp), std::end(dp), 0);
	MW = 30;
	Knapsack();
	int result = 0;
	while (G--) {
	scanf("%d", &MW);
	result += Knapsack();
	}
	printf("%d\n", result);
	}
	}
	int Knapsack()
	{
	if (dp[MW]) return dp[MW];
	int dp[35] = {0};
	for (int i = 0; i < N; ++i) {
	for (int j = MW; j-weight[i] >= 0; --j) {
	dp[j] = std::max(dp[j], dp[j-weight[i]] + price[i]);
	}
	}
	return dp[MW];
	}

view raw [UVa] 10130 SuperSale.cpp hosted with ❤ by GitHub