0 1背包

1.1 题目

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci ,得到的
价值是 Wi 。求解将哪些物品装入背包可使价值总和最大。

1.2 基本思路

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
　　用子问题定义状态:即 F [i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得
的最大价值。则其状态转移方程便是:

• F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下:“将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”,价值为 F [i − 1, v] ;如果放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”,此时能获得的最大价值就是 F [i − 1, v − Ci ] 再加上通过放入第 i 件物品获得的价值 Wi 。

伪代码如下:
　F [0, 0..V ] ← 0
　for i ← 1 to N
　　　for v ← C i to V
　　　　　F [i, v] ← max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=v;j++)//考虑有商品体积为0,但是有价值的情况
            {
                if(j-vom[i]>=0)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vom[i]]+val[i]);
                else dp[i][j]=dp[i-1][j];
            }
        }
        printf("%d\n",dp[n][v]);

1.3 优化空间复杂度

以上方法的时间和空间复杂度均为 O(V N ) ,其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到 O(V ) 。
　　先考虑上面讲的基本思路如何实现,肯定是有一个主循环 i ← 1 . . . N ,每次算出来
二维数组 F [i, 0 . . . V ] 的所有值。那么,如果只用一个数组 F [0 . . . V ] ,能不能保证第 i
次循环结束后 F [v] 中表示的就是我们定义的状态 F [i, v] 呢? F [i, v] 是由 F [i − 1, v] 和
F [i − 1, v − Ci ] 两个子问题递推而来,能否保证在推 F [i, v] 时(也即在第 i 次主循环中
推 F [v] 时)能够取用 F [i − 1, v] 和 F [i − 1, v − Ci ] 的值呢?
　　事实上,这要求在每次主循环中我们以 v ← V . . . 0 的递减顺序计算 F [v] ,这样才
能保证计算 F [v] 时 F [v − Ci ] 保存的是状态 F [i − 1, v − Ci] 的值。

伪代码如下:
　F [0..V ] ←0
　for i ← 1 to N
　　for v ← V to C i
　　　F [v] ← max{F [v], F [v − Ci ] + W i }

其中的 F [v] ← max{F [v], F [v − Ci ] + Wi } 一句,恰就对应于我们原来的转移方程,因
为现在的 F [v − Ci ] 就相当于原来的 F [i − 1, v − Ci ] 。如果将 v 的循环顺序从上面的逆
序改成顺序的话,那么则成了 F [i, v] 由 F [i, v − Ci ] 推导得到,与本题意不符。

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=vom[i];j--)
            {
                dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
            }
        }
        printf("%d\n",dp[v]);

1.4 初始化的细节问题

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目
要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别
这两种问法的实现方法是在初始化的时候有所不同。
　　如果是第一种问法,要求恰好装满背包,那么在初始化时除了 F [0] 为 0 ,其它
F [1..V ] 均设为 −∞ ,这样就可以保证最终得到的 F [V ] 是一种恰好装满背包的最优解。
　　如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 F [0..V ]
全部设为 0 。
　　这是为什么呢?可以这样理解:初始化的 F 数组事实上就是在没有任何物品可以放
入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可以在什
么也不装且价值为 0 的情况下被“恰好装满”,其它容量的背包均没有合法的解,属于
未定义的状态,应该被赋值为 -∞ 了。如果背包并非必须被装满,那么任何容量的背包
都有一个合法解“什么都不装”,这个解的价值为 0 ,所以初始时状态的值也就全部为 0
了。
Bone Collector
不要求背包刚好装满时，dp[]全部初始化为0

#include <cstdio>
#include<algorithm>
#include<string.h>
//#include<iostream>
using namespace std;
int main()
{
    int t;
    int dp[1010],val[1010],vom[1010];
    scanf("%d",&t);
  while(t--)
  {
        int n,v;
        scanf("%d%d",&n,&v);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",val+i);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",vom+i);
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=vom[i];j--)
            {
                dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
            }
        }
        printf("%d\n",dp[v]);
  }
}

0 1背包要求完全装满，dp[1,2,...v]初始化为-∞，dp[0]=0;
如果dp[v]<0，则表示体积为v的背包恰好装满是无解的

#include <cstdio>
#include<algorithm>
#include<string.h>
//#include<iostream>
using namespace std;
int main()
{
    int t;
    int dp[1010],val[1010],vom[1010];
    scanf("%d",&t);
  while(t--)
  {
        int n,v;
        scanf("%d%d",&n,&v);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",val+i);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",vom+i);
        }
        memset(dp,-0x3f3f3f3f,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=vom[i];j--)
            {
                dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
            }
        }
        for(int i=0;i<=v;i++)
        printf("v=%d,val=%d\n",i,dp[i]);
        if(dp[v]<0) printf("No solution!\n");
        else printf("%d\n",dp[v]);

  }
}
/*
input:
1
5 10
1 2 3 4 5
2 4 6 7 8

output:
v=0,val=0
v=1,val=-1044266559
v=2,val=1
v=3,val=-1044266558
v=4,val=2
v=5,val=-1044266557
v=6,val=3
v=7,val=4
v=8,val=5
v=9,val=5
v=10,val=6
6
*/

1.5 一个常数优化

　　ps:这段伪代码中的Ｗi指的是体积(花费)，而不是价值
　　倒推 F(v) 需求出F(v-vom(n)),往后推 F(v-vom(n)),需求出F(v-vom(n)-vom(n-1)) 继续往后推 则推到第i步 为v-sigma(vom[i...n])
　　这个优化对V比较大时效果显著

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1010;
const int VOM=1010;
int dp[VOM];
int val[MAXN];
int vom[MAXN];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,v,sumOfV=0;
        scanf("%d%d",&n,&v);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",val+i);
        }
        vom[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",vom+i);
            sumOfV+=vom[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            sumOfV-=vom[i-1];
            int tmp=max(v-sumOfV,vom[i]);
            for(int j=v;j>=tmp;j--)
            {
                dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
            }
        }
        printf("%d\n",dp[v]);
    }
    return 0;
}