uva10130 - SuperSale（01双肩包）

uva10130 - SuperSale（01背包）

题目：uva10130 - SuperSale（01背包）

题目大意：超市甩卖。有n件商品，每件商品有对应的价值和重量。有一个家族准备去超市买东西，每个人最多每种甩卖商品只能买一件，可以拿很多不同的商品但是要能拿得动。给出每个人能拿得动的最大重量，问这样的一个家族取采购能够得到的最大的价值。

解题思路：01背包。 dp【j】 = Max （dp【j】， dp【j - W】 + P）；W是商品的重量，P是商品的价值。

代码：

#include <cstdio>
#include <cstring>

const int N = 10005;
const int maxn = 35;
int dp[maxn];
int object[N][2];

int Max (const int a, const int b) { return a > b ? a: b; }

int main () {

	int t;
	int n, g;
	int w;
	int ans;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d", &n);
		for (int i = 0; i < n; i++)
			scanf ("%d%d", &object[i][0], &object[i][1]);
		scanf ("%d", &g);

		memset (dp, 0, sizeof (dp));

		for (int i = 0; i < n; i++) 
			for (int j = maxn - 5; j >= object[i][1]; j--)
				dp[j] = Max(dp[j], dp[j - object[i][1]] + object[i][0]);

		ans = 0;
		for (int i = 0; i < g; i++) {

			scanf ("%d", &w);
			ans += dp[w];
		}

		printf ("%d\n", ans);
	}
	return 0;
}