7.9 混合背包问题7.10 特殊要求7.11 背包问题的搜索解法

7.9 混合背包问题

【问题描述】还是背包问题，不过有的物品只能取一次（0/1 背包），有的可以取无限次（完全背包），有的只能取有限次（多重背包）。怎么解决？
由于我们按物品划分阶段，所以没有必要想太多。下面给出伪代码：

for (int i=1; i<N; i++) // 不变
if (物品i属于0/1背包)
{
// 按照0/1背包的做法取物品i
for (int c=C;c>=0;c--)
if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]);
}
else if (物品i属于完全背包)
{
// 按照完全背包的做法取物品i
for (int c=0;c<=C;c++) 
if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]);
}
else if (物品i属于多重背包)
{
// 按照多重背包的做法取物品i
……
}

 7.10 特殊要求

(1) 输出字典序最小的最优方案

这里“字典序最小”的意思是 1～N 号物品的选择方案排列出来以后字典序最小。
一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略：以 0/1 背包为例。在某一阶段，两种决策的结果相同，就应该按照前者来输出方案。

(2) 求方案总数

以 0/1 背包为例。它的状态转移方程为 

除了可以求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
只需把状态转移方程中的 max 改成 sum（求和），并将初始条件设为 f[0][0]=1，就可以通过 f[n-1][C]求出方案总数。
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

 (3) 最优方案的总数

这里的最优方案是指物品总价值最大的方案。以 01 背包为例。
结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：开一个数组 g[i][c]，表示这个子问题的最优方案的总数。在求 f[i][c]的同时，顺便就把 g[i][c]带下来了。
代码如下：

for (int i=1;i<=n;i++)
for (int c=0;c<=C;c++)
{
f[i][c]=f[i-1][c];
if (c>=w[i]) f[i][c] = max(f[i][c], f[i-1][c-w[i]] + v[i]);
g[i][c]=0;
if (f[i][c]==f[i-1][c])
g[i][c] += g[i-1][c];
if (f[i][c] == (f[i-1][c-w[i]] + v[i]))
g[i][c] += g[i-1][c-w[i]] + v[i];
// 注：如果两个状态的值相等，那么计算g时应该把两部分都算进去。这就是必须单独求g的原因。
}

(4) 求次优解、第 K 优解
对于求次优解、第 K 优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第 K 优解则比求最优解的复杂度上多一个系数 K。其基本思想是将每个状态都表示成有序队列，将状态转移方程中的 max/min 转化成有序队列的合并。

以 0/1 背包为例。0/1 背包的状态转移方程为 
如果要求第K 优解，那么状态 f[i][c]就应该是一个大小为 K 的数组 f[i][c][K＋1]。其中 f[i][c][k]表示前 i 个物品、背包大小为 c 时，第 k 优解的值。显然可以认为 f[i][c][K＋1]是一个有序队列。
然后可以说：f[i][c]这个有序队列是由①、②这两个有序队列合并得到的。有序队列①即 f[i－1][c][K]，②则理解为在 f[i－1][c－w[i]][K]的每个数上加上 v[i]后得到的有序队列。合并这两个有序队列并将结果的前 K 项储存到 f[i][c][K＋1]中的复杂度是 O(K)。最后的答案是 f[N][C][K]。总的复杂度是 O(CNK)。实际上，一个正确的状态转移方程的求解过程已经覆盖了问题的所有方案。只不过由于是求最优解，所以其它达不到最优的方案都被忽略了。因此，上面的做法是正确的。
另外，要注意题目对于“第 K 优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。

 7.11 背包问题的搜索解法

(1) 代码

对于 0/1 背包问题，简单的深搜的复杂度是 O(2^n)。就是枚举出所有 2n 种将物品放入背包的方案，然后找最优解。代码如下（调用 try(1,0,0)即可）：

int max=0;
void try(int i, int curw, int curv) // i是当前物体，curw是当前重量，curv是当前的价值
{
if (i>n)
{
if (curv > max) max = curv;
return;
}
if (curw + w[i] <= C) try(i+1, curw + w[i], curv + v[i]);
try(i+1, curw, curv);
}

(2) 预处理和剪枝

预处理：在搜索中，可以认为顺序靠前的物品会被优先考虑。
所以，可以利用贪心的思想，将更有可能出现在结果中的物品的顺序提前，可以较快地得出贪心的较优解，也更有利于最优性剪枝。这需要按照“性价比”（权值/费用）来排列搜索顺序。
另一方面，若将费用较大的物品排列在前面，可以较快地填满背包，有利于可行性剪枝。
最后一种可以考虑的方案是：在开始搜索前将给定的物品的顺序打乱。这样可以避免命题人设置的陷阱。
可行性剪枝：即判断按照当前的搜索路径搜下去能否找到一个可行解，例如：若将剩下所有物品都放入包仍然无法将背包充满（设题目要求必须将背包充满），则剪枝。
最优性剪枝：即判断按照当前的搜索路径搜下去能否找到一个最优解，例如：若加上剩下所有物品的权值也无法得到比当前得到的最优解更优的解，则剪枝。

(3) 搜索还是 DP

在看到一道背包问题时，应该用搜索还是动态规划呢？如果一个背包问题可以用动态规划求解，V 一定不能很大，否则 O(VN)的算法无法承受，而一般的搜索解法都是仅与 N 有关，与 V 无关。
所以，V 很大时，应该优先考虑搜索；N 较大时，应该优先考虑动态规划。
另外，当想不出合适的动态规划算法时，就只能用搜索了。