首页 > 代码库 > HDU3033 I love sneakers!

HDU3033 I love sneakers!

2024-07-14 12:39:43   217人阅读

一道反分组背包，第一次接触这个，还是很不理解，看了好多网上的题解，接着不理解，或许是大神们写的思路和我思考的方向不一样，不过还是找到了比较简洁而又能反映出问题本质的代码，果断收藏贴上来 （没交，不知道是不是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");    }}

 


联系
我们