uva10130 - SuperSale（01背包）

uva10130 - SuperSale（01背包）

題目：uva10130 - SuperSale（01背包）

題目大意：超市甩賣。有n件商品，每件商品有對應的價值和重量。有一個家族准備去超市買東西，每個人最多每種甩賣商品只能買一件，可以拿很多不同的商品但是要能拿得動。給出每個人能拿得動的最大重量，問這樣的一個家族取采購能夠得到的最大的價值。

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

代碼：

#include 
#include 

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