背包问题

前言：背包问题的学习笔记和部分典型例题整理。

01背包

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

最为基础的背包问题。

分析：

1.每种物品都只有一件。
2.都只有放或是不放两种选择。
3.用(f_{i,v})表示只放入前(i)个物品时在所用体积为(v)时所能得到的最大价值。
4.由此可以得出状态转移方程式：(f_{i,v}=max(f_{i-1,v},f_{i-1,v-c_i}+w_i))

解释：

1.这是一个背包问题的原始状态转移方程式，有很多背包问题的变体都是从此推出而得
2.将前(i)个物品放入背包这一过程只会与前(i-1)个物品有关，也就是相当于只考虑第(i)件物品是否放入的问题
3.如果不放入第(i)件物品，那么问题转化为前(i-1)件物品放入容量为(v)的背包中，表示出来就是此时：(f_{i,v}=f_{i-1,v})
4.如果放入第(i)件物品，那么问题转化为前(i-1)件物品放入容量为(v-c_i)的背包中，表示出来就是此时：(f_{i,v}=f_{i-1,v-c_i}+w_i)
5.因为要取其中的最优策略，所以要取两种情况中的较大值

空间复杂度优化：

1.01背包的空间复杂度其实可以优化到(O(N))级别
2.上面讲的思路如果要实现，首先要有一层(1 dots n)的循环，控制每一次循环得出某个(i)时的所有(f_{i,v})的值
3.是否能只用一个一维数组(f_{0 dots v})就保证在第(i)次循环推(f_{i,v})的值时得到的(f_v)就是之前的(f_{i-1,v})和(f_{i-1,v-c_i}+w_i)的值呢？
4.其实在循环时用(v dots 1)的顺序推出(f_v),这样就能保证得到的(f_v)就是(f_{i-1,v})和(f_{i-1,v-c_i}+w_i)中的较大值
5.以下是这个过程的代码

for(int i=1;i<=n;i++)
    for(int j=m;j>=1;j--)
        f[j]=max(f[j-c[i]]+w[i],f[j]);

一些细节：

1.其实可以对上面的代码进行一个常数优化，因为如果循环中的(j)比当前的(c_i)要小，便没有继续推的必要，可以把for(int j=m;j>=1;j--)改为for(int j=m;j>=c[i];j--)
2.如果要求的是恰好装满背包情况下的最大价值，那么除了(f_0)赋值为(0),除此之外的(f_{1 dots m})都要赋为极小值(-infty)
3.如果要求的是不必装满背包情况下的最大价值（比如下面那道模板题），那么整个(f_{0 dots m})都赋值为(0)
4.分成这两种情况的原因是：初始化数组(f)时应该给其赋值在没有任何物品放入时的合法状态
5.如果要求恰好装满，那么没有物品情况下的唯一合法情况就是容量为(0)的情况被“一无所有”装满时的价值(0),其他容量的背包均无合法的解，处于未定义状态，所以赋值为(-infty)
6.如果不要求恰好装满，那么此时每个容量下的背包都有合法情况即不装任何物品，所以(f_{0 dots m})都赋值为(0)
7.关于初始化的问题可以推广到其他种类的背包问题

例题：

P1048 采药
纯01背包模板，不要求装满 code