学习笔记——背包问题

从良月澪二大佬那学的背包九讲

一.01背包问题

众所周知，01背包是一个较为简单的DP问题（万恶之源），从他开始，我们将正式迈入DP的殿堂（死亡的深渊），所以掌握01背包是以后所有背包问题的基础，需要OIer认真学习。

1.01背包的基本问题描述

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

2.01背包问题的特点：

每种物品仅有一件，可以选择放或不放。

3.01背包问题的基本思路

设$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−w[i]$的背包中”，此时能获得的最大价值就是 $f[i−1][j-w[i]]$ 再加上通过放入第i件物品获得的价值$v[i]$。

4.01背包空间复杂度的优化

仔细观察可知，$f[i][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]]$的值。

注：如果顺序推的话，可能会使$f[i][j]$的值覆盖掉$f[i-1][j]$的值，影响我们所要求的真实值，导致程序出错。

所以有如下代码

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]=max(f[j],f[j−w[i]])$ 一句恰就相当于我们的转移方程$f[i][j]=max(f[i−1][j],f[i−1][j−w[i]])$，因为现在的$f[j−w[i]]$就相当于原来的$f[i−1][j−w[i]]$。如果将$V $的循环顺序从上面的逆序改成顺序的话，那么则成了$f[i][j]由f[i][j−w[i]]$ 推来，不是我们所要求的值。

其实，这一串代码还可以优化

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<w[i]$时，$f[j]$的状态时不会改变的，所以只用让$j$从$V$循环到$w[i]$即可，减少循环次数。

5.初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。

1.要求恰好装满背包时的最优解

这样的话，在初始化时除了$f[0]$为$0$其它$f[1->V]$均设为 $-$$ \infty $，这样就可以保证最终得到的$f[N]$是一种恰好装满背包的最优解。

解释：初始化的$f$数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为$0$的背包可能被价值为$0$的$nothing$“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该为$−$$\infty$了。

2.没有要求必须把背包装满时的最优解

如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为$0$，所以初始时状态的值也就全部为$0$了。

这个小技巧完全可以推广到其它类型的背包问题

6.终极优化（防止一些毒瘤出题人卡常）（小bb:应该没有怎么丧心病狂的人吧）

前面的代码中有$for(j=V->w[i])$，还可以将这个循环的下限进行改进。由于只需要最后$f[j]$的值，倒推前一个物品，其实只要知道$f[j−w[n]]$即可。以此类推，对以第$j$个背包，其实只需要知道到$f[j−sum(w[j->n])]$ 即可，即代码可以改成

for(int i=1;i<=n;i++) cin>>w[i]>>v[i],s[i]=s[i-1]+w[i];
for(int i=1;i<=n;i++){
	int bound=max(w[i],V-(s[n]-s[i]));
	for (int j=V;j>=bound;j--)
		f[j]=max(f[j],f[j-w[i]]+v[i]);
}
           

7.小结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

好了，01背包的讲解就到这里吧（反正我也写不动了）。

来补几道练手题

1.裸的01背包板子（01背包详细教程）（我的代码）

2.重量=价值的简单01背包（记得用总重量减去最大价值）（不错的题解）（我的代码）

3.求填满01背包的方案数（新颖的DP题）（思路讲解的不错的题解）（我的代码）

4.01背包变种--手动求价值（集结了所有背包板子良心题解）（我的代码）

5.看似很难实则数据范围造就白给的水题（以新奇思路优化DP的题解）（我的代码）

6.多个体积维度的01背包（讲的很详细的题解）（我的代码）

Update:2020.10.29

二、完全背包问题

1.完全背包问题的基本问题描述

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

2.完全背包问题的特点：

每一件物品都有很多件，可以无限选择。

3.完全背包问题的基本思路

仍然按照解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)
           

解释：因为$k$表示选该件物品的次数，所以$k$可以有不选到全部选满（使背包中再也装不下该件物品）之间的所有选择。

这跟01背包问题一样有$O(VN)$个状态需要求解，但求解每个状态的时间已经不是常数了$（O(1)）$。因为求解状态$f[i][j]$的时间是$O(V/w[i])$，所以总的时间复杂度可以认为是$O(N\times\sum(V/w[i]))$，这个时间复杂度是比较大的。

对于完全背包问题与01背包问题的联系的感悟：

将01背包问题的基本思路加以改进，得到了这样一个清晰的解决完全背包问题方法,这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。

4.一个常数优化

（一）、若两件物品$i$、$j$满足$w[i]\leqslant w[j]$且$v[i]\geqslant v[j]$，则将物品j去掉，不用考虑。

正确性证明：在任何情况下，将一个价值小但费用高的物品换成一个（或多个）价值高且费用低的物品一定能使所求的总价值最高，那这个价值小但费用高的物品就可以不用在循环DP求解时考虑，可以有效的减少循环的次数。

对于一些可能遇到的情况进行分析：

（1）当该数据为随机生成时：因为可能每一个物品都相差很大，所以可以删去大量的无用数据（状态），大大减少运算量，提高程序运行的效率。

（2）当该数据为（毒瘤）出题人精心（丧心病狂）的构造的时：因为出题人会让每一个物品都无法被删去，所以无法减少时间复杂度，反而会负优化。

这个优化可以简单的 $O(n^2)$处理

（二）、首先将费用大于V的物品去掉，然后使用类似计数排序的做法，只保留费用相同的物品中价值最高的，就可以$O(V+N)$地完成这个优化。

5.将完全背包问题转化为01背包问题求解

首先，我们脑海中肯定是想将完全背包问题转化为01背包问题求解（毕竟我们已经学会了01背包问题），那我们可以将一个物品分成$V/w[i]$份（出现了，物品分身术！），再将其用01背包的方法求解。

显然，这样做的时间复杂度太大了，那我们可不可以换一种跟快的方法呢？当然可以，毕竟已经有人帮我们想过了（让我们站在巨人的肩膀上）。

把第i种物品拆成费用为$w[i]\times 2^k$,价值为$v[i]\times 2^k$的$k$件物品，其中$k$满足$w[i]\times 2^k\le V$。因为不管最优策略选几件第i种物品，总可以表示成若干个$2^k$件物品的和。这样，我们就可以把每种物品拆成$O(log(V/w[i]))$件物品,用二进制的原理降低时间复杂度。

当然，人们还是嫌他太慢了，所以又发明了$O（VN）$的神奇算法。

这个算法使用一维数组，代码如下

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]);
           

怎么样，是不是感觉很简单？是不是有一种似曾相识的感觉？没错，这就是我从01背包问题中的代码搬过来的（大雾）这就是改了一下j的循环次序，让j顺序查找。

那么，本着知其然要知其所以然的心态，我们来细细研究一下这其中的妙处。首先，通过回忆01背包，我们可以记得逆序修改是为了让每一个物品都只被选一次，那同理可得，顺序修改是为了让DP中该物品有可能被多次选中，这样既不用让该物品分身又可以提速，何乐而不为呢？

6.小结

完全背包问题也是一个相当基础的背包问题，他有以下两个DP方程式

f[i][j]=max(f[i−1][j−k*w[i]]+k*v[i])(0<=k*w[i]<=j)

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]);

           

需要OIer仔细地体会，不仅记住，也要弄明白他们是怎么得出来的，最好能够自己想一种得到这些方程的方法。（理解性记忆肯定比死记硬背更牢固）

事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。

老规矩，上题。

1.完全背包的板子题（和01背包板子一模一样的题面可还行）（题解）（我的代码（其实就改一下循环顺序，01背包代码就变成的完全背包代码））

2.和第一题题面不同的完全背包板子（讲解01背包和完全背包差异的题解）（第一题的代码（大雾 ）

3.可以通过数据范围减少DP次数的水题（题解）（我的代码）

4.要点脑子的完全背包（一语点醒梦中人的题解）（我的代码）

这道题让我学会了放慢节奏做题，不要一昧的追求速度，要仔细看清题面。例如本题还要考虑买的多还更便宜的情况。

好了，这个背包的学习笔记将要咕很长一段时间了（别问为什么，问就是要马上复习复赛的知识点，考完复赛后还要疯狂补文化，估计以后要随缘更新了。那么，有缘再会吧！）

Update 2020.11.24

我又回来了，既然要面对即将到来的NOIP，我当然又停课学OI了。（停课一时爽，月考火葬场）不管怎么说，还是先开启我们的背包之旅吧！

三、多重背包问题

1.多重背包问题的基本问题描述

有$N$件物品和一个容量为$V$的背包，第$i$件物品最多有$p[i]$件可用，每一件的费用都是$w[i]$,价值都是$v[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

2.多重背包问题的特点：

每一件物品都有有限件。

3.多重背包问题的基本思路

数学教遇到新的问题不会怎么办？转化啊！把它变成我们熟悉的01背包不就好了。但是很明显，如果把每一种物品都拆分成$p[i]$件，那时间复杂度就变成了$O(V \times \sum p[i])$，(这复杂度不得上天)

所以，人们又想到了另一种方法--二进制拆分

4.二进制拆分

方法是：将第$i$种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为$1，2，4$, . . . , $2{k-1}$,$p[i]-2{k}+1$，且$k$是满足$p[i]-2^{k}+1>0$的最大整数。这样就将第$i$种物品分成了$O(log(p[i]))$件物品，将原问题转化为了复杂度为$O(V\times \sum log(p[i]))$的01背包问题。代码如下

for (int i = 1; i <= n; i++) {
    int num = min(p[i], V / w[i]);//num表示最多可以取的物品数
    for (int k = 1; num > 0; k <<= 1) {//注意，k要不断*2进行拆分
        if (k > num) k = num;//最后一步防止多取物品，令k为num，这样可以表示完所有0到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);
    }
}
           

5.单调队列优化

这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊$O(1)$的时间求解。

这个代码暂时看不懂，所以扔完代码我就闪了

其实一般不会有毒瘤出题人将时限卡的这么死，所以掌握好二进制拆分就够了

//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;
        }
    }
}
           

好了，又到了刷题时间

弱化版

1.简单的多重背包板子(还没我跑的快的题解(看思路就好，代码自己打))(我的代码)

2.自己定义价值维度的意义的多重背包问题(详细讲解价值维度定义方法的题解)(我的代码)

注意：对于一些题目不能总想着优化后的代码，要学会返璞归真，从最初的思路开始解题。例如本题就不能使用二进制拆分，而要一个一个地枚举。

求装满完全背包的方案数(良心题解，记录了所有做法(包括搜索、记搜、DP、滚动数组、一维DP、前缀和优化))(我的代码)

可行性问题

1.统计该容量能否被表示的完全背包问题(讲的详细的题解)(我的代码)

2.贪心+完全背包问题(一语点醒梦中人的题解)(我的代码)

经验教训：即使对于一些看似简单的背包题，也要考虑是否夹杂了其他算法。例如本题要使用贪心进行优化，才能得出正确的答案。

二进制优化/单调队列优化

1.二进制优化的完全背包的板子(二进制优化的题解)(详细讲解单调队列优化的题解)(我的代码)

四、混合背包问题

如果将前面三个背包混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢？

2.多重背包问题的基本思路

1.01背包+完全背包

考虑到在01背包和完全背包中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是$O(VN)$。(具体一点，就是一类物品只能取一次，就用逆序的循环，一类物品可以取无限次，就用顺序的循环)

2.再加上多重背包

如果再加上有的物品最多可以取有限次，那么原则上也可以给出$O(VN)$的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过$NOIP$范围的算法的话，用多重背包中将每个这类物品分成$O(log p[i])$个01背包的物品的方法也已经很优了。

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]);
           

在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。这就体现了编程中抽象的威力。如果你一直就是以这种 "抽象出过程"的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同（顺序、逆序和二进制拆分），那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法。

小结

有人说，困难的题目都是由简单的题目叠加而来的，它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。

老规矩，上几道题来练手

1.多重+完全背包(有图的题解)(我的代码)

本题也要重新定义价值这一维度，令最少消耗的硬币数为价值，然后在一定范围内找最小硬币和。

2.01+完全背包问题(详细的题解)(我的代码)

本题一定要注意DP的顺序，理清思路，按顺序写代码，不然可能像我一样被一个DP顺序调了一个晚上

五、二维费用背包问题

1.二维费用背包问题的基本问题描述

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价$1$和代价$2$，第$i$件物品所需的两种代价分别为$w[i]$和$g[i]$。两种代价可付出的最大值（两种背包容量）分别为$V$和$T$。物品的价值为$v[i]$。

2.二维费用背包问题的基本思路

费用加了一维，只需状态也加一维即可。设$f[i][j][k]$表示前$i$件物品付出两种代价分别为$j$和$k$时可获得的最大价值。状态转移方程就是：$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i]][k-g[i]])$

如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量$j$和$k$采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包问题时拆分物品。代码：(假设都为01背包)

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        for (int k = T; k >= g[i]; k--)
            f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
           

3.物品总个数的限制

有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取$M$件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为$1$，可以付出的最大件数费用为$M$。换句话说，设$f[i][j]$表示付出费用$i$、最多选$j$件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在$f[0......V][0......M]$范围内寻找答案。

4.复数域上的背包问题

另一种看待二维背包问题的思路是：将它看待成复数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复数。而常见的一维背包问题则是实数域上的背包问题。（注意：上面的话其实不严谨，因为事实上我们处理的都只是整数而已。）所以说，一维背包的种种思想方法，往往可以应用于二维背包问题的求解中，因为只是数域扩大了而已。

扔几道特别水的例题

1.二维费用背包问题的板子(题解)(我的代码)

2.又是一道水题板子(详细的题解（话说水题还要题解？）)(我的代码)

3.再来一道水题板子（好了好了，之后不刷水题了）(题解)(我的代码)

4.五维背包+离散化思想的捆绑销售优惠题(暴力题解（直接五维费用01+完全背包硬刚）)(我的代码)

六、分组背包问题

1.分组背包问题的基本问题描述

给定$N$组物品，其中第$i$组有$C_i$个物品。第$i$组物品的第$j$个物品的体积为$V_{ij}$，价值为$W_{ij}$。有一个容量为$M$的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过$M$的前提下，使物品的价值总和最大。

2.分组背包问题的基本思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设$f[i][j]$表示前$i$组物品花费费用$j$能取得的最大权值，则有：

$$F[i][j]= max \begin{cases} F[i-1][j] \text{不选第i组的物品}\ \max\limits_{1\le k\le C_i}F[i-1][j-V_{ij}]+W_{ik} \text{选第i组的某个物品k}\end{cases}$$

和前面所学的背包问题一样，我们可以滚掉前一维，用$j$的逆序循环来控制“阶段$i$”的状态只能由“阶段$i-1$”的状态转移而来。下面给出代码：

memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=n;++i)
	for(int j=m;j;--j)
		for(int k=1;k<=c[i];++k)
			if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);               
           

其中的$v[i][k]$表示第$i$组物品的第$k$个物品的体积，$w[i][k]$表示第$i$组物品的第$k$个物品的价值。

注意：对于每一组的$c[i]$个物品的循环，$k$应该放在$j$的内层。因为如果$k$在外层，就会产生类似完全背包的效果（上一个物品选完后，这一个物品接着上一个物品的状态继续更新导致错误），选择超过$1$个的物品。

分组背包的例题

1.最裸的板子(分组背包模板的题解)(我用另一种处理方式打的代码)

本题主要考选手如何将物品分组，我选择浪费一点时间来换取空间，sort一遍后再找物品对应组号进行转移，题解大部分用空间来换取时间，用二维数组存储然后进行状态转移。

2.隐藏的分组背包(sort用得出神入化的题解)(我的代码)

本题让我了解到了sort的新一种用法--对二维数组的某一维度进行排序，就可以极大地降低时间复杂度，方便之后的操作。

七、有依赖背包问题

1.有依赖背包问题的基本问题描述

这种背包问题的物品间存在某种“依赖”的关系。也就是说，$i$依赖于$j$，表示若选物品$i$，则必须选物品$j$。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

2.有依赖背包问题的基本思路

这个问题由$NOIP2006$年金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。

按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件…无法用状态转移方程来表示如此多的策略。（事实上，设有 $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$个物品的物品组，就可以直接应用分组背包的算法解决问题了。

3.较一般的问题

更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上，这是一种树形$DP$，其特点是每个父节点都需要对它的各个儿子的属性进行一次$DP$以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完泛化物品后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

4.小结

拿金明的预算方案来说，通过引入“物品组”和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。

例题

1.博客中例子的原题(工程代码，变量名好评)(我的代码)

2.树形DP好题（大雾（记得要用分组背包）(树形DP的题解)(我的代码)

八、泛化物品

1.定义

考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。

更严格的定义是：在背包容量为$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 \times w$，其它函数值均为$0$。如果它是多重背包中重复次数最多为$n$的物品，那么它对应的泛化物品的函数有$h(v)=v / c \times w$仅当$v$被$c$整除且$v/c \le n$，其它情况函数值均为$0$。一个物品组可以看作一个泛化物品$h$。对于一个$0......V$中的$v$，若物品组中不存在费用为$v$的的物品，则$h(v)=0$，否则$h(v)$为所有费用为$v$的物品的最大价值。有依赖的背包问题中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。

2.泛化物品的和

如果面对两个泛化物品$h$和$l$，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用$v$，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于$0......V$的每一个整数$v$，可以求得费用$v$分配到$h$和$l$中的最大价值$f(v)$。也即

$$f(v)=max(h(k)+l(v-k)) (0\leqslant k\leqslant v)$$

可以看到，$f$也是一个由泛化物品$h$和$l$决定的定义域为$0......V$的函数，也就是说，$f$是一个由泛化物品$h$和$l$决定的泛化物品。

由此可以定义泛化物品的和：$h$、$l$都是泛化物品，若泛化物品$f$满足以上关系式，则称$f$是$h$与$l$的和。这个运算的时间复杂度取决于背包的容量，是$\Theta (V^2)$。

泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为$s$，则答案就是$s[0......V]$中的最大值。

3.背包问题的泛化物品

一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数$v$求得：若背包容量为$v$，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品--或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域（例如$0......V$）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。

综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。

4.背包问题问法的变化

之前讲的都是给定背包容量求其可以得到的最大价值，但其实背包还有很多变化的问题（如最多可以放入几件物品、最多可以装满体积为多少的背包等），需要OIer在做题时随机应变（毕竟学OI最重要的是学会一种思想，然后将这一种思想应用到其他问题中）。

1.输出方案

我们可以用一个数组记录下每个状态的最优值是由状态转移方程的哪一项推出来的（它是由那一个决策得到的），然后从最终状态递归的往上一状态推导，直到回到初始状态。

以01背包为例：

$$F[i][j]== \begin{cases} F[i-1][j] \text{不选第i组的物品}\ F[i-1][j-V[i]]+W[i] \text{选第i个物品}\end{cases}$$

然后将选择的物品加入ans数组，再逆序输出即可。

2.输出字典序最小的最优方案

首先我们要理解题意--字典序最小指的是选择的$1......N$号物品的选择方案排列出来以后字典序最小。

还是以01背包为例子

在该问题中，我们只用考虑在进行状态转移是保证最终选择的是字典序最小即可，那我们就对状态转移方程下手。01背包的状态转移方程想必大家都比较熟悉了吧，

$$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$$

当$f[i-1][j]=f[i-1][j-w[i]]+v[i]$时，我们一定要选择当前的物品，这样就可以保证字典序最小（因为当前物品的编号小于后面物品的编号，与其用后面物品编号大的来组成答案序列，不如先用这个物品编号小的来组成（贪心），反正这个不行后面也会被覆盖掉，这个行就使答案序列的字典序更小了）。

3.求方案总数

简单来说，就是求将背包装到某一容量时的方案总数。

对于这一类问题，先将初始化时$f[0][0]=1$，然后将背包问题的状态转移方程中$max$转化为$\sum$即可。还是那01背包当栗子吧

$$f[i][j]=f[i-1][j]+f[i-1][j-w[i]]$$

可行性原因：状态转移方程已经考察了所有可能的背包组成方案。

4.最优方案的总数

这里的最优方案是指物品总价值最大的方案。

还是那个万年不变的例子（谁让它最简单呢）

我们可以再新开一个数组（设为$g[i][j]$），令其记录$f[i][j]$的最优解方案数（$f[i][j]$由多个状态都可以得到则$++g[i][j]$，若$f[i][j]$更新为一个新的最大值，则将$g[i][j]$重置为$1$）。

5.求第$K$优解

首先我们要知道，如果该问题的最优解可以写出DP方程式，那么该问题的第$K$优解往往可以由同样的时间复杂度得到，并且在时间上比最优解多一个系数$K$。

思路：将每一个状态都表示为有序队列，将状态转移方程中的$max$转化为有序队列的合并。

还是那个万年不变的例子（01背包）

因为我们要求的是第$K$优解，所以我们可以在DP数组上新开一维，表示这一状态的第$K$优解，即$f[i][j][k]$表示用前$i$件物品装满容量为$j$的背包的第$K$优解的值。那么我们的DP方程式也相应变成了

$$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i]][k]+v[i])$$

最终答案为$f[n][m][k]$,时间复杂度为$\Theta(NMK)$。

代码如下(将策略不同但权值相同的两个方案是看作同一个解)

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];
}

           

#include <iostream>
#include <cstdio>
#include <complex>
#define A 1000010
using namespace std;
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];
}