首页 > 代码库 > hdu3033（变形分组背包）
hdu3033（变形分组背包）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3033
题意：Iserlohn要买鞋，有k种牌子，每种牌子至少买一双鞋子。每双鞋子有标价跟实际价值。求用m多的钱买最多价值的鞋。
分析：分组背包是有k组物品，每组至多取一件或不取，用容量为v的背包装最多价值的物品。而这题是至少每组取一件。
状态方程dp[k][m] 表示已经买了k种鞋 在有m钱状态下的鞋的最大价值。
为了满足至少每组取一件，则加了这组状态转移方程：
if(dp[k-1][j-b[i]]+c[i]!=-1)dp[k][j]=max(dp[k][j],dp[k-1][j-b[i]]+c[i]);
初始化dp数组为-1很重要，若dp[k][j]=-1,说明该种状态无法达到。
dp[0]全部置为0，就是为了满足第一种能一定在v体积范围内一定取得到，同样只要剩余的空间满足第二种物品体积，那么它也会一定取得道，这样每种种物品第一件会把dp[k]数组更新为一遍，所以当该种物品还有多件物品时，就可用01背包取或不取来进行决策。即
if(dp[k][j-b[i]]!=-1)dp[k][j]=max(dp[k][j],dp[k][j-b[i]]+c[i])
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;int dp[15][N],a[110],b[110],c[110];int main(){ int n,m,kind; while(scanf("%d%d%d",&n,&m,&kind)>0) { for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); memset(dp,-1,sizeof(dp)); memset(dp[0],0,sizeof(dp[0])); for(int k=1;k<=kind;k++) for(int i=1;i<=n;i++)if(a[i]==k) for(int j=m;j>=b[i];j--) { if(dp[k][j-b[i]]!=-1)dp[k][j]=max(dp[k][j],dp[k][j-b[i]]+c[i]); if(dp[k-1][j-b[i]]!=-1)dp[k][j]=max(dp[k][j],dp[k-1][j-b[i]]+c[i]); } if(dp[kind][m]==-1)puts("Impossible"); else printf("%d\n",dp[kind][m]); }}
hdu3033（变形分组背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。