完全背包

 

完全背包： 

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。  完全背包按其思路仍然可以用一个二维数组来写出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

 

同样可以转换成一维数组来表示:

伪代码如下:

1 2 3

for i=1..N    for v=0..V        f[v]=max{f[v],f[v-weight[i]]+value[i]}

顺序

 

想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。

现在关键的是考虑：为何完全背包可以这么写？
看一下填表过程，是从左到右填的，因为你一个物品可以拿多个，而且我们比较的是没加入当前背包f[v]（上一行）与下一行f[v-weight[i]]+value[i]的大小

在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。 那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？ 因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。

 

这里同样给大家一道题目： 

题目： 

代码： 

这道题是求最小价值，不是最大

题目大意：给定一个储蓄罐可容纳的重量和n个价值为p重量为w的硬币，问在填满储蓄罐的情况最小的价值为多少？如果没办法填满输出This is impossible.

解题思路：因为题目的数据范围很小，时间又给很多，可以直接暴力，枚举每次选的数量后相当于01背包

3 10 110(可容纳的重量=110-10,后面减去前面的) 2 1 1(value,weight) 30 50 以上是一个测试用例 10 110 2 1 1 50 30 1 6 2 10 3 20 4 

Sample Output

The minimum amount of money in the piggy-bank is 60. 

The minimum amount of money in the piggy-bank is 100. 

This is impossible.

一开始record数组开小了，搞到一直WA

#include<stdio.h>

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        int value[501],weight[501],record[10001];
        int i,j;
        int c1,c2;
        scanf("%d%d",&c1,&c2);
        int c=c2-c1;
        int n;//n<=500;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&value[i],&weight[i]);
        }
        for(i=1;i<=c;i++)
            record[i]=-1;
        record[0]=0;
        for(i=1;i<=n;i++)
        {
            for(j=weight[i];j<=c;j++)
            {
                //最后归结为两种情况，题目是求最小价值
                //这是最正常的情况比较
                if( record[j-weight[i]]!=-1 && record[j]!=-1 )
                {

                    if(record[j]>(record[j-weight[i]]+value[i]))//第i件商品,求最小值所以是大于
                        record[j]=record[j-weight[i]]+value[i];

                }
                //j-weight[i]肯定是首个record[0]为0，record[9,10,11,12,13,14,15,16,...,-9]
                //如果record[j]==-1；那么就不必要比较，直接record[j]=record[j-weight[i]]+value[i];
                //record[9]我已经计算到，record[10]我没必要算(留着以后算)，但record[18]我要算，因为刚好两个9
                else if(record[j-weight[i]]!=-1 && record[j]==-1 )
                {
                    record[j]=record[j-weight[i]]+value[i];

                }
            }
        }
         if(record[c] != -1)
            printf("The minimum amount of money in the piggy-bank is %d.\n",record[c]);
        else
            printf("This is impossible.\n");
    }

    return 0;
}