首页 > 代码库 > HDU 3033 I love sneakers! 分组背包
HDU 3033 I love sneakers! 分组背包
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3033
题意:有N种鞋,手里有M元,N种鞋属于K种品牌,(1<=N<=100,1 <= M<= 10000,1<=K<=10),每双鞋有自己的价格和价值,每种品牌的鞋至少要买一双,问最多能够买到多少价值的鞋。
思路:背包问题的变种,把要装入背包的物品分成了若干类,并且对于每种物品的选取有限制,(一般为至少选一个或者至多选一个,本题是至少选一个),由于所有物品被分了组,那么处理第i类的时候就要对前i-1类分包的结果进行处理。
状态转移方程:for(i=1;i<=K;i++)
for(j=0;j<top[i];j++)
for(k=M;k>=pro[i][j][0];k--)
dp[i][k]=max(dp[i][k],dp[i-1][k-pro[i][j][0]]+pro[i][j][1],dp[i][k-pro[i][j][0]+pro[i][j][1]);
其中i代表第i类物品,j代表第i类物品第j个,k代表背包空间。这样转移可以保证每次转移得到的结果都能保证本类物品至少选择一个。
代码:
#include <iostream> #include <cstdio> #include <cstring> #define maxm 15 #define maxn 105 #define maxb 100005 using namespace std; int pro[maxm][maxn][2]; int dp[maxm][maxb],top[maxm]; void init() { memset(dp,-1,sizeof(dp)); memset(pro,0,sizeof(pro)); memset(top,0,sizeof(top)); dp[0][0]=0; } int main() { int N,M,K,b; while(~scanf("%d%d%d",&N,&M,&K)) { init(); for(int i=0; i<N; i++) { scanf("%d",&b); scanf("%d%d",&pro[b][top[b]][0],&pro[b][top[b]][1]); top[b]++; } bool flag = 0; for(int i=1; i<=K; i++) { if(!top[i]) { flag = 1; break; } for(int j=0; j<top[i]; j++) for(int k=M; k>=pro[i][j][0]; k--) { if(dp[i][k-pro[i][j][0]]!=-1) dp[i][k]=max(dp[i][k-pro[i][j][0]]+pro[i][j][1],dp[i][k]); if(dp[i-1][k-pro[i][j][0]]!=-1) dp[i][k]=max(dp[i-1][k-pro[i][j][0]]+pro[i][j][1],dp[i][k]); } } int ans = -1; for(int i=0; i<=M; i++) if(dp[K][i]>ans) ans=dp[K][i]; if(ans==-1||flag) puts("Impossible"); else printf("%d\n",ans); } return 0; }
HDU 3033 I love sneakers! 分组背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。