HDU 1114 完全背包 HDU 2191 多重背包

HDU 1114　Piggy-Bank 完全背包问题、

想想我们01背包是逆序遍历是为了保证什么？

保证每件物品只有两种状态，取或者不取.那么正序遍历呢？这不就正好满足完全背包的条件了吗

means:给出小猪钱罐的重量和装满钱后的重量，然后是几组数据，每组数据包括每种钱币的价值与重量要求出装满钱罐时的最小价值

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 using namespace std;

 const int qq=+;

 const int MAX=1e8;

 int dp[qq];

 int v[qq],p[qq];

 int main()

 {

     int t;scanf("%d",&t);

     while(t--){

         int a,b;scanf("%d%d",&a,&b);

         int c=b-a;

         int n;scanf("%d",&n);

         for(int i=;i<n;++i)

             scanf("%d%d",&p[i],&v[i]);

         for(int i=;i<=c;++i)

             dp[i]=MAX;

         dp[]=;

         for(int i=;i<n;++i)

             for(int j=v[i];j<=c;++j)

                 dp[j]=min(dp[j],dp[j-v[i]]+p[i]);

         if(dp[c]==MAX)    printf("This is impossible.\n");

         else            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[c]);

     }

     return ;

 }

HDU 2191 多重背包问题、

其实还是应用01背包的思想、不过这里有一个小技巧就是二进制表示法、

比如 13、可以表示成 1+2+4+5 这4个数可以组成1到13之间的任意一个数、

那么就可以多重背包拆分成01背包问题、

千万注意将空间压缩成一维的话是逆序遍历、这里解释一下 dp数组中的每一个值都是一种状态，该种状态在当前是独立的不受其他影响的，如果正序遍历的话前面得到的一些状态影响其他状态的生成、

- -、我是这么理解的、总之你要dp的话就是... 唉本弱弱语文水平好差、

联想一下二维数组下是怎么更新状态的、再看看一维、这样就很容易理解了

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int qq=;

 int p[qq],v[qq];

 int dp[qq];

 int main()

 {

     int t;scanf("%d",&t);

     while(t--){

         int price,kind;

         scanf("%d%d",&price,&kind);

         int count=;

         int a,b,c;

         for(int i=;i<kind;++i){

             scanf("%d%d%d",&a,&b,&c);

             int t=;

             while(c>=t){

                 p[count]=a*t;

                 v[count++]=b*t;

                 c=c-t;

                 t=t<<;

             }

             if(c){

                 p[count]=a*c;

                 v[count++]=b*c;

             }

         }

         for(int j,i=;i<count;++i)

             for(j=price;j>=p[i];--j)

                 dp[j]=max(dp[j],dp[j-p[i]]+v[i]);

         printf("%d\n",dp[price]);

         memset(dp,,sizeof(dp));        //一定记得初始化、毕竟有很多组数据、

     }

     return ;

 }

巴特西

HDU 1114 完全背包 HDU 2191 多重背包

最新文章

热门文章