首页 > 代码库 > HDU3033 I love sneakers!
HDU3033 I love sneakers!
一道反分组背包,第一次接触这个,还是很不理解,看了好多网上的题解,接着不理解,或许是大神们写的思路和我思考的方向不一样,不过还是找到了比较简洁而又能反映出问题本质的代码,果断收藏贴上来 (没交,不知道是不是AC代码,主要是还自己从里头学点东西了~~)
#include <stdio.h>const int N=101,oo=100000000;int f[11][10001],c[N],w[N],b[N];void main(){ int n,v,s,i,j,k; while (scanf("%d%d%d",&n,&v,&s)!=EOF) { for (i=1;i<=n;i++) scanf("%d%d%d",&b[i],&c[i],&w[i]); for (j=0;j<=v;j++) f[0][j]=0; for (i=1;i<=s;i++) for (j=0;j<=v;j++) f[i][j]=-oo;//初始化为-oo for (k=1;k<=s;k++) for (i=1;i<=n;i++) if (b[i]==k) for (j=v;j>=c[i];j--)//循环的顺序 { if (f[k][j]<f[k][j-c[i]]+w[i]) f[k][j]=f[k][j-c[i]]+w[i]; if (f[k][j]<f[k-1][j-c[i]]+w[i]) f[k][j]=f[k-1][j-c[i]]+w[i];//先f[k],再f[k-1],有费用为0的物品 } if (f[s][v]>=0) printf("%d\n",f[s][v]); else printf("Impossible\n"); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。