HDU - 3449 Consumer(有依赖的背包问题)
发布时间:2020-12-13 22:14:17 所属栏目:百科 来源:网络整理
导读:题目大意:有N个箱子,每个箱子需要花费Ai的代价 箱子里面有K个物品,K个物品你可以选择买任意个,但每个物品只能买一个,每个物品有相应的花费和价值 你又M的钱,最多能得到多少价值 解题思路:这题我用滚动数组 先处理出买了当前箱子的情况,然后在买了当
题目大意:有N个箱子,每个箱子需要花费Ai的代价 解题思路:这题我用滚动数组 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int dp[N][2];
void solve() {
memset(dp,0,sizeof(dp));
int pair,box,cost,val;
for (int num = 1; num <= n; num++) {
scanf("%d%d",&box,&pair);
//买了箱子
for (int i = m; i >= box; i--)
dp[i][1] = dp[i - box][0];
//不买箱子
for (int i = box - 1; i >= 0; i--)
dp[i][1] = dp[i][0];
for (int p = 0; p < pair; p++) {
scanf("%d%d",&cost,&val);
for (int i = m; i >= box + cost; i--) {
dp[i][1] = max(dp[i][1],dp[i - cost][1] + val);
}
}
//取最大值
for (int i = 0; i <= m; i++)
dp[i][0] = max( dp[i][0],dp[i][1]);
}
int ans = 0;
for (int i = 0; i <= m; i++)
ans = max(dp[i][0],ans);
printf("%dn",ans);
}
int main() {
while (scanf("%d%d",&n,&m) != EOF) {
solve();
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |