01背包：
有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]，求将哪些物品装入背包可使价值总和最大
思路：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
F[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i])
“将前i件物品放入容量为j的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i−1件物品的问题。如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为j的背包中”，价值为f[i−1][j]；如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为j−c[i]的背包中”，此时能获得的最大价值就是f[i−1][j−w[i]]再加上通过放入第i件物品获得的价值v[i]
优化空间复杂度
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1...N，每次算出来二维数组f[i][0...V]的所有值。如果只用一个数组f[0...V]，能不能保证第i次循环结束后f[j]中表示的就是我们定义的状态f[i][j]呢？
f[i][j]是由f[i−1][j]和f[i−1][j−w[i]]两个子问题递推而来，能否保证在推f[i][j]时（也即在第i次主循环中推f[j]时）能够得到f[i−1][j]和f[i−1][j−w[i]]的值呢？事实上，这要求在每次主循环中我们以j=V...0的顺序推f[j]，这样才能保证推f[j]时f[j−w[i]]保存的是状态f[i−1][j−w[i]]的值
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
现在的f[j−w[i]]就相当于原来的f[i−1][j−w[i]]
如果将V的循环顺序从上面的逆序改成顺序的话，则成了f[i][j]由f[i][j−w[i]]推知，与本题意不符，但它却是另一个重要的背包问题（完全背包）最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
写成j=V...0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度
可以加入优化。费用为w[i]的物品不会影响状态f[0...j−1]，这是显然的
初始化的细节问题
求最优解的背包问题题目中，事实上有两种不太相同的问法
有的题目要求"恰好装满背包"时的最优解，有的题目则并没有要求必须把背包装满
这两种问法的区别是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0,其它f[1...V]均设为−∞,就可以保证最终得到的f[N]是一种恰好装满背包的最优解
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0...V]全部设为0
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是−∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解
常数优化
前面的代码中有for(j=V...w[i])，还可以将这个循环的下限进行改进。
由于只需要最后f[j]的值，倒推前一个物品，其实只要知道f[j−w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[j−sumw[j...n]]即可
for (int i = 1; i <= n; i++) {
int bound = max(V - sum{w[i]...w[n]}, v[i]);
for (int j = V; j >= bound, j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
} //对于求sum可以用前缀和，这对于V比较大时是有用的
完全背包：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
思路：这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种
如果仍然按照解01背包时的思路，令f[i][j]表示前i种物品恰放入一个容量为V的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程
F[i][j] = max(f[i - 1][j - k * w[i]] + k * v[i]) 0<= k * w[i] <=j
这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][j]的时间是O(V/w[i])，总的复杂度可以认为是O(N∗Σ(V/w[i]))，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度
一个简单有效的优化
若两件物品i j满足w[i]<=w[j]且v[i]>=v[j]，则将物品j去掉不用考虑。
这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
这个优化可以简单的O(N^2)地实现，一般都可以承受。
另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化
转化为01背包求解
最简单的想法是，考虑到第i种物品最多选V/w[i]件，于是可以把第i种物品转化为V/w[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品
更高效的转化方法是：把第i种物品拆成费用为w[i]∗2^k、价值为v[i]∗2^k的若干件物品，其中k满足w[i]*2^k<=V,这是二进制的思想，不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/w[i]))件物品，是一个很大的改进
O(VN)的算法
for (int i = 1; i <= n; i++)
for (int j = 0; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
这个代码与01背包的代码只有j的循环次序不同而已
为什么这样一改就可行呢？
首先想想为什么01背包中要按照j=V...0的逆序来循环(要保证第i次循环中的状态f[i][j]是由状态f[i−1][j−w[i]]递推而来)换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i−1][j−w[i]]
而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][j−w[i]]，所以就必须采用j=0...V的顺序循环,值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以以另外的思路得出。例如，将基本思路中求解f[i][j−w[i]]的状态转移方程显式地写出来，代入原方程中，会发现该方程可以等价地变形成这种形式：
F[i][j] = max(f[i - 1][j],f[i][j - w[i]] + v[i])
多重背包：
有N种物品和一个容量为V的背包。第i种物品最多有p[i]件可用，每件费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
思路：
与完全背包类似：F[i][j] = max(f[i - 1][j - k * w[i]] + k * v[i]) 复杂度是O(V∗Σp[i])
另一种思路是转化成01背包：二进制拆分
for (int i = 1; i <= n; i++) {
int num = min(number[i], V / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = V; j >= w[i] * k; j--)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
}
}
O(VN)的算法
基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解
代码如下（需要外套1...n1...n 1...n1...n循环）
//p：某类物品数量，w：某类物品花费，v：某类物品价值，V:商品总价值
void MultiPack(int p, int w, int v) {
for (int j = 0; j < w; j++) { //j为w的所有组
int head = 1, tail = 0;
for (int k = j, i = 0; k <= V / 2; k += w, i++) {
int r = f[k] - i * v;
while (head <= tail and r >= q[tail].v) tail--;
q[++tail] = node(i, r);
while (q[head].id < i - p) head++; //需要的物品数目
f[k] = q[head].v + i * v;
}
}
}
单调队列，就是在区间移动时动态维护区间的最值
观察它的转移方程：f[i][j]=max(f[i−1][j],f[i−1][j−k∗w[i]]+k∗v[i])，单调队列优化的主要思想就是分组更新，因为w[i]是成倍增加的f[i−1][j]只会更新f[i−1][j+k∗w[i]]（这里是从前往后看的，所以是+）
对于当前为w的体积，我们可以按照余数将它分为w组，也就是0...w−1同一个剩余系的数在一组
比如在模3意义下，1,4,7,10是一组，2,5,8,11是一组，3,6,9,12是一组
每组的转移是互不影响的，也就是单独转移
举个例子
f[i][5w]=max(f[i−1][4w]+w,f[i−1][3w]+2v,f[i−1][2w]+3v,f[i−1][w]+4v,f[i−1][0]+5v)
f[i][4w]=max(f[i−1][3w]+w,f[i−1][2w]+2v,f[i−1][w]+3v,f[i−1][0]+4v)
让所有的f[i][j]都减去j/w∗v，式子就变成
f[i][5w]=max(f[i−1][4w]−4v,f[i−1][3w]−3v,f[i−1][2w]−2v,f[i−1][w]−v,f[i−1][0])
f[i][4w]=max(f[i−1][3w]−3v,f[i−1][2w]−2v,f[i−1][w]−v,f[i−1][0])
即f[i][j]=max(f[i−1][j mod w+k * w]−k * v+j * v)
当j mod w一定后，就可以用单调队列来优化了
混合背包：
将前面三个背包混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢
01背包与完全背包的混合
考虑到在01背包和完全背包中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)
加上多重背包
p[i]:每个物品的件数，0代表无穷个
for (int i = 1; i <= n; i++)
if (p[i] == 0)
for (int j = w[i]; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
else
for (int k = 1; k <= p[i]; k++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
二维费用背包：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为w[i]和g[i]。两种代价可付出的最大值（两种背包容量）分别为V和T，物品的价值为v[i]
思路：设f[i][j][k]表示前i件物品付出两种代价分别为j和k时可获得的最大价值。状态转移方程就是：f[i][j][k]=maxf[i−1][j][k],f[i−1][j−w[i]][k−g[i]]+v[i]
如前述方法，使用二维数组：当每件物品只可以取一次时变量j和k采用逆序的循环，当物品有如完全背包问题时采用顺序循环。当物品有如多重背包问题时拆分物品
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
for (int k = T; k >= g[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - w[i]][k - g[i]] + v[i]);
物品总个数限制
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。
换句话说，设f[i][j]表示付出费用i、最多选j件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0...V][0...M]范围内寻找答案
复数域上的背包问题
将它看待成复数域上的背包问题，背包的容量以及每件物品的费用都是一个复数。而一维背包则是实数域上的背包问题，所以一维背包的种种思想方法可以应用于二位背包问题的求解中，只是数域扩大了而已
分组背包：
有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][j]表示前k组物品花费费用j能取得的最大权值
F[k][j] = max(f[k - 1][j],f[k - 1][j - c[i]] + w[i]) 物品i属于组k
for (所有的组k)
for (int j = V; j >= 0; j--)
for (所有属于组k的i)
f[j] = max{f[j], f[j - w[i]] + v[i]}
注意三层循环的顺序，for(j...0)这一层循环必须在for(所有的i属于组k)之外，才能保证每一组内的物品最多只有一个会被添加到背包中。
显然可以对每组内的物品应用完全背包中“一个简单有效的优化”
小结：
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如有依赖的背包），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题
有依赖背包：
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j，简化起见，先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品
思路：
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。
但是可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件…无法用状态转移方程来表示如此多的策略。（n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（只能选择一种策略），一个主件和它的附件集合实际上对应于分组背包中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑分组背包中的一句话： 可以对每组中的物品应用完全背包中“一个简单有效的优化”，这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。
我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0...V−c[i]所有这些值时相应的最大价值f′[0...V−c[i]]，这个主件及它的附件集合相当于V−c[i]+1个物品的物品组，其中费用为c[i]+k的物品的价值为f′[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V−c[i]+1个物品的物品组，就可以直接应用分组背包的算法解决问题了
较一般问题
依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完泛化物品后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和
泛化物品：
考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义：在背包容量为V的背包问题中，泛化物品是一个定义域为0...V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)，另一种理解是一个泛化物品就是一个数组h[0...V]，给它费用v，可得到价值h[V]
一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c∗w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/c∗w仅当v被c整除且v/c<=n，其它情况函数值均为0。一个物品组可以看作一个泛化物品h。对于一个0...V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v)为所有费用为v的物品的最大价值。有依赖的背包问题中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品
泛化物品的和
面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了
同样的，对于0...V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)
F[v] = max(h(k) + l(v - k)| 0 <= k <= v)
f也是一个由泛化物品h和l决定的定义域为0...V的函数(f是一个由泛化物品h和l决定的泛化物品)
由此定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足以上关系式，则称f是h与l的和,运算时间复杂度O(V^2)
泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0...V]中的最大值
背包问题的泛化物品
一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品（给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品）
这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息，一般而言，求得这个泛化物品的一个子域（例如0...V）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。
综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之
背包问题问法的变化
以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到，还有，如果要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可
输出方案
一般背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，也就是记录下它是由哪一个策略推出来的，便可根据这条策略找到上一个状态，从上一个状态接着向前推即可
还是以01背包为例，方程为f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
再用一个数组g[i][j]，设g[i][j]=0表示推出f[i][j]的值时是采用了方程的前一项（也即f[i][j]=f[i−1][j]），g[i][j]=1表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品，最终状态为f[N][V]
另外，采用方程的前一项或后一项也可以在输出方案的过程中根据f[i][j]的值实时地求出来，不须纪录g数组，将上述代码中的g[i][j]==0改成f[i][j]==f[i−1][j]，g[i][j]==1改成f[i][j]==f[i−1][j−w[i]]+v[i]也可。
输出字典序最小的最优方案
“字典序最小”的意思是1...N号物品的选择方案排列出来以后字典序最小
以输出01背包最小字典序的方案为例,一般求一个字典序最小的最优方案，只需要在转移时注意策略,首先子问题的定义要略改一些。如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为j−w[1]，物品为2...N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2...N的子问题,不管答案怎样，子问题的物品都是以i...N而非前所述的1...i的形式来定义的，所以状态的定义和转移方程都需要改一下
但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][j]==f[i−1][i−j]及f[i][j]==f[i−1][j−w[i]]+v[i]同时成立，应该按照后者（即选择了物品i）来输出方案
求方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可
例如若每件物品均是完全背包中的物品，转移方程即为f[i][j]=∑f[i−1][j],f[i][j−w[i]]
初始条件f[0][0]=1,事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案
最优方案的总数
这里的最优方案是指物品总价值最大的方案以01背包为例。
结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[i][j]意义同前述，g[i][j]表示这个子问题的最优方案的总数，则在求f[i][j]的同时求g[i][j]
求次优解、第K优解
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K
基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并
以01背包为例:首先看01背包求最优解的状态转移方程：f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
要求第K优解，那么状态f[i][j]就应该是一个大小为K的数组f[i][j][1...K],其中f[i][j][k]表示前i个物品、背包大小为j时，第k优解的值。“f[i][j]是一个大小为K的数组”可以简单地理解为在原来的方程中加了一维。显然f[i][j][1...K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。然后原方程就可以解释为：f[i][j]这个有序队列是由f[i−1][j]和f[i−1][j−w[i]]+v[i]这两个有序队列合并得到的
有序队列f[i−1][j]即f[i−1][j][1...K]，f[i−1][j−w[i]]+v[i]则理解为在f[i−1][j−w[i]][1...K]的每个数上加上v[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][j][1...K]中的复杂度是O(K),最后的答案是f[N][V][K]。总的复杂度是O(VNK)。
为什么这个方法正确呢？一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的
int kth(int n, int V, int k) {
for (int i = 1; i <= n; i++) {
for (int j = V; j >= w[i]; j--) {
for (int l = 1; l <= k; l++) {
a[l] = f[j][l];
b[l] = f[j - w[i]][l] + v[i];
}
a[k + 1] = -1;
b[k + 1] = -1;
int x = 1, y = 1, o = 1;
while (o != k + 1 and (a[x] != -1 or b[y] != -1)) {
if (a[x] > b[y]) f[j][o] = a[x], x++;
else f[j][o] = b[y], y++;
if (f[j][o] != f[j][o - 1]) o++;
}
}
}
return f[V][k];
}
背包问题的搜索解法
简单的深搜
对于01背包问题，简单深搜的复杂度是O(2^N),枚举出所有2^N种将物品放入背包的方案，然后找最优解
搜索的剪枝
可行性剪枝即判断按照当前的搜索路径搜下去能否找到一个可行解，例如：若将剩下所有物品都放入背包仍然无法将背包充满（设题目要求必须将背包充满），则剪枝。
最优性剪枝即判断按照当前的搜索路径搜下去能否找到一个最优解，例如：若加上剩下所有物品的权值也无法得到比当前得到的最优解更优的解，则剪枝。
搜索的顺序
在搜索中，顺序靠前的物品会被优先考虑。利用贪心思想，将更有可能出现在结果中的物品的顺序提前，可以较快得出贪心地较优解，更有利于最优性剪枝。可以考虑将按照“性价比”（权值/费用）来排列搜索顺序。另一方面，若将费用较大的物品排列在前面，可以较快地填满背包，有利于可行性剪枝。最后一种可以考虑的方案是：在开始搜索前将输入文件中给定的物品的顺序随机打乱。这样可以避免命题人故意设置的陷阱。以上三种决定搜索顺序的方法很难说哪种更好，事实上每种方法都有适用的题目和数据，也有可能将它们在某种程度上混合使用
子集和问题
子集和问题是一个NP−Complete问题，与前述的（加权的）01背包问题并不相同。给定一个整数的集合S和一个整数X，问是否存在S的一个子集满足其中所有元素的和为X,这个问题有一个时间复杂度为O(2^(N/2))的较高效的搜索算法，其中N是集合S的大小
第一步思想是二分。将集合S划分成两个子集S1和S2,大小都是N/2,对于S1和S2，分别枚举出它们所有的2^(N/2)个子集和，保存到某种支持查找的数据结构中，例如hashset。然后将两部分结果合并，寻找是否有和为X的S的子集。事实上，对于S1的某个和为X1的子集，只需寻找S2是否有和为X−X1的子集。假设采用的hashset是理想的，每次查找和插入都仅花费O(1)的时间。两步的时间复杂度显然都是O(2^(N/2)),
实践中，往往可以先将第一步得到的两组子集和分别排序，然后再用两个指针扫描的方法查找是否有满足要求的子集和。这样的实现，在可接受的时间内可以解决的最大规模约为N=42
搜索还是DP?
首先可以从数据范围中得到命题人意图的线索,如果一个背包问题可以用DP解，V一定不能很大，否则O(VN)的算法无法承受，而一般的搜索解法都是仅与N有关而与V无关，所以V很大时（例如上百万），命题人的意图就应该是考察搜索，另一方面，N较大时（例如上百），命题人的意图就很有可能是考察动态规划
题目简解
加权01背包问题，也就是说：每种物品只有一件，只可以选择放或者不放；而且每种物品有对应的权值，目标是使总权值最大或最小。它最朴素的状态转移方程是：f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
f[i][j]表示前i件物品花费代价j可以得到的最大权值。w[i]和v[i]分别是第i件物品的花费和权值,则f[i]的求解过程就是使用第i件物品对f[i−1]进行更新的过程。那么就不用使用二维数组，只需要定义f[j]，然后对于每件物品i，顺序地检查f[j]与f[j−w[i]]+v[i]的大小，如果后者更大，就对前者进行更新。这是背包问题中典型的优化方法
每种物品的使用量没有直接限制，但使用物品的总量有限制。求第一个不能用这有限个物品组成的背包的大小。（可以这样等价地认为）设f[k][i]表示前k件物品组成大小为i的背包最少需要物品的数量。则
f[k][i]=min(f[k−1][i],f[k−1][i−j∗s[k]]+j)
其中j是选择使用第k件物品的数目，这个方程运用时可以用和上面一样的方法处理成一维的。求解时先设置一个粗糙的循环上限，即最大的物品乘最多物品数。
多重背包问题，要求解的是构成一种背包的不同方案总数，就是把多重背包方程中的min改成sum就行
多重背包，要求求解所给的物品不能恰好放入的背包大小的最大值（可能不存在）。只需要根据“若ij 互质，则关于x、y的不定方程i∗x+y∗j=n必有正整数解，其中n > i*j”这一定理得出一个循环的上限
int f[A], w[A], v[A];
/*---------0-1背包----------*/
int knapsack01(int n, int V) {
memset(f, 0xc0c0c0c0, sizeof f); f[0] = 0; //需要装满
memset(f, 0, sizeof f); //不需要装满
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
return f[V];
}
/*-----------完全背包----------*/
int Fullbackpack(int n, int V) {
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
return f[V];
}
/*-------多重背包二进制拆分-------*/
int number[A];
int MultiplePack1(int n, int V) {
for (int i = 1; i <= n; i++) {
int num = min(number[i], V / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = V; j >= w[i] * k; j--)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
}
}
return f[V];
}
int newv[A], neww[A], cnt;
int MultiplePack2(int n, int V) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c[i]; j <<= 1) {
newv[cnt] = j * v[i];
neww[cnt++] = j * w[i];
c[i] -= j;
}
if (c[i] > 0) {
newv[cnt] = c[i] * v[i];
neww[cnt++] = c[i] * w[i];
}
}
for (int i = 1; i <= cnt; i++)
for (int j = V; j >= neww[i]; j--)
f[j] = max(f[j], f[j - neww[i]] + newv[i]);
return f[V];
}
/*------------多重背包单调队列优化------------*/
void MultiPack(int p, int w, int v) {
for (int j = 0; j < cost; j++) {
int head = 1,tail = 0;
for (int k = j, i = 0; k <= V / 2; k += w, i++) {
int r = f[k] - i * v;
while (head <= tail and r >= q[tail].v) tail--;
q[++tail] = node(i, r);
while (q[head].id < i - num) head++;
f[k] = q[head].v + i * v;
}
}
}
/*-----------二维费用背包----------*/
int t[A], g[A], dp[B][B];
int Costknapsack(int n, int V, int T) {
for (int i = 1; i <= n; i++)
for (int j = T; j >= w[i]; j--)
for (int k = V; k >= g[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - w[i]][k - g[i]] + v[i]);
return dp[T][V];
}
/*--------------分组背包--------------*/
int a[B][B];
int Groupingbackpack() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= j; k++)
f[j] = max(f[j], f[j - k] + a[i][k]);
return f[m];
}
/*------------K优解---------------*/
int kth(int n, int V, int k) {
for (int i = 1; i <= n; i++) {
for (int j = V; j >= w[i]; j--) {
for (int l = 1; l <= k; l++) {
a[l] = f[j][l];
b[l] = f[j - w[i]][l] + v[i];
}
a[k + 1] = -1;
b[k + 1] = -1;
int x = 1, y = 1, o = 1;
while (o != k + 1 and (a[x] != -1 or b[y] != -1)) {
if (a[x] > b[y]) f[j][o] = a[x], x++;
else f[j][o] = b[y], y++;
if (f[j][o] != f[j][o - 1]) o++;
}
}
}
return f[V][k];
}
京公网安备 11010502036488号