01背包

转自：
首先我们把三种情况放在一起来看： 

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包， 每种物品均只有一件。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

多重背包(MultiplePack): 有N种物品和一个容量为V的背包，第i种物品最多有n[i]件可用。每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。 

 

先来分析01背包： 

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包，每种物品均只有一件。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： 

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把这个过程理解下：

在前i件物品放进容量v的背包时，它有两种情况

情况一: 第i件不放进去，这时所得价值为:f[i-1][v]

情况二: 第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i] 

（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品） 

最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。  （这里是重点，理解！） 

 

这里是用二维数组存储的，可以把空间优化，用一维数组存储。 

用f[0..v]表示，f[v]表示把前i件物品放入容量为v的背包里得到的价值。把i从1~n(n件)循环后，最后f[v]表示所求最大值。

这里f[v]就相当于二维数组的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重点！思考）

首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。

即：for i=1..N

现在思考如何能在是f[v]表示当前状态是容量为v的背包所得价值，而又使f[v]和f[v-c[i]]+w[i]标签前一状态的价值？ 

逆序

这就是关键！ 

1 2 3

for i=1..N     for v=V..0  f[v]=max{f[v],f[v-c[i]]+w[i]};

分析上面的代码：当内循环是逆序时，就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的！这里给大家一组测试数据：  测试数据： 10,3 3,4 4,5 5,6
（两层循环，对于每个物品，从最大容量开始，一直把从f(10),f(9),...,把每个可容的最大价值标记上f()=record[j]）
                 当第二个物品要加进来，f[v]=Max {f[v-c[i]]+w[i],f[v]} 里面的f[v]是指还没更新的，加进去就是更新了，所以比较一下要不要更新，这样f()就记录了每个f[v]对应的最大值record[v] v=1,2,3,4,5,6,7,8,9,10,（内层循环向左）如：i=2时,f(10,i=1)=4, f(10-4)+5=f(6,i=1)+5=9,所以最较大值9
然后外层循环物品每个逐步加进来（向下）

                                           图2: 01背包图(1)

 

这个图表画得很好，借此来分析： 

C[v]从物品i=1开始，循环到物品3，期间，每次逆序得到容量v在前i件物品时可以得到的最大值。

（请在草稿纸上自己画一画）

这里以一道题目来具体看看： 

题目：

题目大意：从给定各种价值和体积的物品中选取n件，装进容积为v背包。 问最多背

包中能装多少价值的东西。

5 10(n<=1000 v<=1000)

1 2 3 4 5 (每一件对应的 价值 )value[1002]

5 4 3 2 1 (每一件的重量)weight[1002]

问最多背包中能装多少价值的东西。

14

#include
#include
int value[50001],weight[50001],record[50001];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int i,j;
        int N,V;//m<=2000,v<=50000
        scanf("%d%d",&N,&V);//物品种类，背包容量
        for(i=1;i<=N;i++)
        {
            scanf("%d",&value[i]);//(价值)
        }
        for(i=1;i<=N;i++)
        {
            scanf("%d",&weight[i]);//(重量)
        }
        memset(record,0,sizeof(record));
        record[0]=0;
        for(i=1;i<=N;i++)
        {
            for(j=V;j>=0;j--)
            {

                if( j-weight[i]>=0 && (record[j-weight[i]]+value[i])>record[j])
                {
                        record[j]=record[j-weight[i]]+value[i];

                }


            }
        }

            printf("%d\n",record[V]);

    }

    return 0;
}