SuperSale UVA - 10130
01背包
题目描述：一家人去超市买东西，各种物品有价格和重量，每个人都有自己的背包容量，求这一家人能够获得最大价值。
解题分析：刚开始被这题给唬住了，想成了如果一个物品被某人买了，则其他人不可以卖这个物品，那这就难了。但是想想也该明白那家超市一种物品只卖一件啊，超时的物品是任意多的。这题就是单纯的01背包。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000 + 10;
int v[maxn];
int w[maxn];
int dp[maxn];
int peo[maxn];
int N,M;
int main()
{
int kase;
cin >> kase;
while(kase--)
{
memset(dp,0,sizeof(dp));
cin >> N;
for(int i = 1; i <= N; i++)
{
scanf("%d %d",&v[i],&w[i]);
}
cin >> M;
for(int i = 0; i < M; i++)
{
scanf("%d",&peo[i]);
}
for(int i = 1; i <= N; i++)
{
for(int j = 30; j >= w[i]; j--)
{
dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
}
}
int ans = 0;
for(int i = 0; i < M; i++) ans += dp[peo[i]];
cout << ans << endl;
}
return 0;
}
查看14道真题和解析
库洛游戏公司福利 32人发布
