一道反分组背包，第一次接触这个，还是很不理解，看了好多网上的题解，接着不理解，或许是大神们写的思路和我思考的方向不一样，不过还是找到了比较简洁而又能反映出问题本质的代码，果断收藏贴上来 （没交，不知道是不是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");
}
}
HDU3033 I love sneakers!,布布扣,bubuko.com
原文：http://www.cnblogs.com/GJKACAC/p/3874278.html