https://www.showapi.com/book/view/2011/0
https://book.yunzhan365.com/eoph/daev/mobile/index.html#p=4
http://www.yanglajiao.com/article/yukunqi/77721001
https://www.jianshu.com/p/d2320331fb2a
可以将空间优化为
观察问题，两行更新时，用上一行的前部分更新下一行的后部分。
所以单行更新时要从后往前遍历，这样可以用前面的更新后面的。
这个算法也可以从另外的思路中得出，例如，基本思路中的公式可以化作这个形式：
用函数封装：
如果要进行优化的话，依然用二进制思想，同上。
这样可以将时间优化为
多重背包 单调队列
https://kxp555.coding.me/2017/08/27/bag4-9/
4 混合三种背包问题
4.1 问题
如果将前面1、2、3中的三种背包问题混合起来。也就是说，有的物品只可以取一
次（01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限
（多重背包）。应该怎么求解呢？
4.2 01 背包与完全背包的混合
考虑到01 背包和完全背包中给出的伪代码只有一处不同，故如果只有两类物品：
一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程
时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(V N)。伪代码如下
如果再加上最多可以取有限次的多重背包式的物品，那么利用单调队列，也可以给
出均摊O(V N) 的解法。
但如果不考虑单调队列算法的话，用将每个这类物品分成O(logMi) 个01 背包的物
品的方法也已经很优了
在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现
了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每一类背包问题
的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一
定能很快想到上面简洁的解法，对吗？
4.4 小结
有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不
论，但它在本讲中已经得到了充分的体现。本来01 背包、完全背包、多重背包都不是
什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。
但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单
的题目来解决
背包九讲（五）- 二维费用的背包问题
第七讲 有依赖的背包问题
https://book.yunzhan365.com/eoph/daev/mobile/index.html#p=4
http://www.yanglajiao.com/article/yukunqi/77721001
https://www.jianshu.com/p/d2320331fb2a
有N 件物品和一个容量为V 的背包。放入第i 件物品耗费的费用是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。
1.2 基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i; v] 表示前i 件物品恰放入一个容量为v 的背包可以获得的最大价值。则其状态转移方程便是：
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前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。
伪代码如下：
for(i=0;i<w;i++)
{
if(i>=w1[0])
{
dp_1[0][i]=v[0];
}
else
{
dp_1[0][i]=0;
}
}
for(i=1;i<n;i++)
{
for(int j=0;j<=w;j++)
{
if(j>=w1[i])
{
dp_1[i][j]=max(dp_1[i-1][j],dp_1[i-1][j-w1[i]]+v[i]);
}
else
{
dp_1[i][j]=dp_1[i-1][j];
}
}
}
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] 的值。伪代码如下：
for(i=0;i<n;i++)
{
cin>>wi>>pi;
if(i==0)
{
for(j=0;j<=w;j++)
{
if(j>=wi)
{
dp[j]=pi;
}
else
{
dp[j]=0;
}
}
}
else
{
for(j=w;j>=wi;j--)
{
dp[j]=max(dp[j],dp[j-wi]+pi);
}
}
}
cout<<dp[w]<<endl;
其中的F[v] =max｛fF[v], F[v - Ci] +Wi｝ 一句，恰就对应于我们原来的转移方程，因为现在的F[v - Ci] 就相当于原来的F[i - 1, v - Ci]。如果将v 的循环顺序从上面的逆序改成顺序的话，那么则成了F[i, v] 由F[i, v - Ci] 推导得到，与本题意不符。
对于为什么需要逆序从v到0遍历而不是从0到v遍历，我们来举例子具体化的说明一下
而如果逆序的话，你会发现F数组当前索引的值的计算依赖于前面索引的值，不会使用到被更新过的值。这样F数组就能在i-1的情况下完成i趟遍历的更新。
空间优化（滚动数组）
初始状态方程的空间复杂度是O(V*W)，可以进一步优化。可以将空间优化为
O(2*W)，即纵向大小为2。for(i=1; i<=N; i++){
for(j=t[i]; j<=V; j++)
f[t^1][j] = max(f[c][j-w[i]]+c[i], f[t][j]);
t ^= 1;
}
空间优化（一维数组）
既然可以用两行进行更新，那为什么不能用一行。观察问题，两行更新时，用上一行的前部分更新下一行的后部分。
所以单行更新时要从后往前遍历，这样可以用前面的更新后面的。
for(i=1; i<=N; i++)
for(j=V; j>=w[i]; j--)
f[j] = max(f[j-w[i]]+c[i], f[j]);
可以写成函数，封装起来。
void ZeroOnePack(int cost, int weight){
for(int i=V; i>=weight; i++)
f[i] = max(f[i], f[i-weight]+cost)
}
1.4 初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了F[0] 为0，其它F[1…V ] 均设为-∞，这样就可以保证最终得到的F[V ] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F[0…V ]全部设为0。这是为什么呢？可以这样理解：初始化的F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0 的背包可以在什么也不装且价值为0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解。
1.5 一个常数优化
上面伪代码中的for i 1 to Nfor v V to Ci中第二重循环的下限可以改进。它可以被优化为
这个优化之所以成立的原因请读者自己思考。（提示：使用二维的转移方程思考较易。）
01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成01 背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。
2 完全背包问题
2.1 题目
有N 种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i 种物品的费用是Ci，价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。
2.2 基本思路
这个问题非常类似于01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0 件、取1 件、取2
件……直至取⌊V /Ci⌋ 件等许多种。如果仍然按照解01 背包时的思路，令F[i; v] 表示前i 种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
这个问题非常类似于01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0 件、取1 件、取2
件……直至取⌊V /Ci⌋ 件等许多种。如果仍然按照解01 背包时的思路，令F[i; v] 表示前i 种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
这跟01 背包问题一样有O(V N) 个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态F[i,v] 的时间是O(v/Ci)，总的复杂度可以认为是O(NV ∑ V/Ci)，是比较大的。将01 背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01 背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是要试图改进这个复杂度。
2.3 一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j 满足Ci ≤ Cj且Wi ≥ Wj，则将可以将物品j 直接去掉，不用考虑。这个优化的正确性是显然的：任何情况下都可将价值小费用高的j 换成物美价廉的i，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
这个优化可以简单的O(N^2) 地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V + N) 地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。
O(N^2) 优化部分代码：
就是先将数值赋值到一个数组，然后进行比较处理掉不符合规则的数值，再重新赋值到另一个数组中去。
2.4 转化为01 背包问题求解
01 背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为01 背包问题来解。
最简单的想法是，考虑到第i 种物品最多选⌊V /Ci⌋ 件，于是可以把第i 种物品转化为⌊V /Ci⌋ 件费用及价值均不变的物品，然后求解这个01 背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为01 背包问题的思路：将一种物品拆成多件只能选0 件或1 件的01 背包中的物品。更高效的转化方法是：把第i 种物品拆成费用Ci * 2^k、价值为Wi * 2^k 的若干件物品，其中k 取遍满足Ci*2^k ≤ V 的非负整数。这是二进制的思想。因为，不管最优策略选几件第i 种物品，其件数写成二进制后，总可以表示成若干个2^k 件物品的和。这样一来就把每种物品拆成O(log ⌊V /Ci⌋) 件物品，是一个很大的改进。
最简单的想法是，考虑到第i 种物品最多选⌊V /Ci⌋ 件，于是可以把第i 种物品转化为⌊V /Ci⌋ 件费用及价值均不变的物品，然后求解这个01 背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为01 背包问题的思路：将一种物品拆成多件只能选0 件或1 件的01 背包中的物品。更高效的转化方法是：把第i 种物品拆成费用Ci * 2^k、价值为Wi * 2^k 的若干件物品，其中k 取遍满足Ci*2^k ≤ V 的非负整数。这是二进制的思想。因为，不管最优策略选几件第i 种物品，其件数写成二进制后，总可以表示成若干个2^k 件物品的和。这样一来就把每种物品拆成O(log ⌊V /Ci⌋) 件物品，是一个很大的改进。
2.5 O(V N) 的算法
这个算法使用一维数组，先看伪代码：
你会发现，这个伪代码与01 背包问题的伪代码只有v 的循环次序不同而已。
为什么这个算法就可行呢？首先想想为什么01 背包中要按照v 递减的次序来循环。让v 递减是为了保证第i 次循环中的状态F[i; v] 是由状态F[i - 1, v - Ci] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i 件物品”这件策略时，依据的是一个绝无已经选入第i 件物品的子结果F[i -1, v - Ci]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i 种物品”这种策略时，却正需要一个可能已选入第i 种物品的子结果F[i, v-Ci]，所以就可以并且必须采用v递增的顺序循环。这就是这个简单的程序为何成立的道理。
值得一提的是，上面的伪代码中两层for 循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以由另外的思路得出。例如，将基本思路中求解F[i,v -Ci] 的状态转移方程显式地写出来，代入原方程中，会发现该方程可以等价地变形成这种形式：
为什么这个算法就可行呢？首先想想为什么01 背包中要按照v 递减的次序来循环。让v 递减是为了保证第i 次循环中的状态F[i; v] 是由状态F[i - 1, v - Ci] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i 件物品”这件策略时，依据的是一个绝无已经选入第i 件物品的子结果F[i -1, v - Ci]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i 种物品”这种策略时，却正需要一个可能已选入第i 种物品的子结果F[i, v-Ci]，所以就可以并且必须采用v递增的顺序循环。这就是这个简单的程序为何成立的道理。
值得一提的是，上面的伪代码中两层for 循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以由另外的思路得出。例如，将基本思路中求解F[i,v -Ci] 的状态转移方程显式地写出来，代入原方程中，会发现该方程可以等价地变形成这种形式：
for(i=0;i<3;i++)
{
for(int j=0;j<=money;j++)
{
if(j>=v[i])
{
dp_1[j]=max(dp_1[j],dp_1[j-v[i]]+v[i]);
}
}
}
cout<<money-dp_1[money]<<endl;
O(VN)算法
for(int i=1; i<=N; i++)
for(int j=w[i]; j<=V; j++)
f[j] = max{f[v], f[v-w[i]]+c[i]};
这个算法也可以从另外的思路中得出，例如，基本思路中的公式可以化作这个形式：
f[i][v]=max(f[i-1][v], f[i][v-w[i]]+c[i]);用函数封装：
void CompletePack(int cost, int weight){
for(int i=weight; i<=V; i++)
f[i] = max(f[i], f[i-weight]+cost);
}
将这个方程用一维数组实现，便得到了上面的伪代码。
最后抽象出处理一件完全背包类物品的过程伪代码：
最后抽象出处理一件完全背包类物品的过程伪代码：
2.6 小结
完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程。希望读者能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。
事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
3 多重背包问题
3.1 题目
有N 种物品和一个容量为V 的背包。第i 种物品最多有Mi 件可用，每件耗费的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
3.2 基本算法
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。因为对于第i 种物品有Mi + 1 种策略：取0 件，取1 件……取Mi 件。令F[i, v]表示前i 种物品恰放入一个容量为v 的背包的最大价值，则有状态转移方程：
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。因为对于第i 种物品有Mi + 1 种策略：取0 件，取1 件……取Mi 件。令F[i, v]表示前i 种物品恰放入一个容量为v 的背包的最大价值，则有状态转移方程：
3.3 转化为01 背包问题
另一种好想好写的基本方法是转化为01 背包求解：把第i 种物品换成Mi 件01背包中的物品，则得到了物品数为∑Mi 的01 背包问题。直接求解之，复杂度仍然是O(V ∑Mi)。
但是我们期望将它转化为01 背包问题之后，能够像完全背包一样降低复杂度。
仍然考虑二进制的思想，我们考虑把第i 种物品换成若干件物品，使得原问题中第i 种物品可取的每种策略——取0…Mi 件——均能等价于取若干件代换以后的物品。另外，取超过Mi 件的策略必不能出现。方法是：将第i 种物品分成若干件01 背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1、 2、2^2 … 2^k-1,Mi - 2^k + 1，且k 是满足Mi - 2^k + 1 > 0 的最大整数。例如，如果Mi为13，则相应的k = 3，这种最多取13 件的物品应被分成系数分别为1、2、4、6 的四件
物品。
另一种好想好写的基本方法是转化为01 背包求解：把第i 种物品换成Mi 件01背包中的物品，则得到了物品数为∑Mi 的01 背包问题。直接求解之，复杂度仍然是O(V ∑Mi)。
但是我们期望将它转化为01 背包问题之后，能够像完全背包一样降低复杂度。
仍然考虑二进制的思想，我们考虑把第i 种物品换成若干件物品，使得原问题中第i 种物品可取的每种策略——取0…Mi 件——均能等价于取若干件代换以后的物品。另外，取超过Mi 件的策略必不能出现。方法是：将第i 种物品分成若干件01 背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1、 2、2^2 … 2^k-1,Mi - 2^k + 1，且k 是满足Mi - 2^k + 1 > 0 的最大整数。例如，如果Mi为13，则相应的k = 3，这种最多取13 件的物品应被分成系数分别为1、2、4、6 的四件
物品。
分成的这几件物品的系数和为Mi，表明不可能取多于Mi 件的第i 种物品。另外这种方法也能保证对于0 …Mi 间的每一个整数，均可以用若干个系数的和表示。这里算法正确性的证明可以分0… 2^(k-1) 和2k…Mi 两段来分别讨论得出，希望读者自己思考尝试一下。
这样就将第i 种物品分成了O(logMi) 种物品， 将原问题转化为了复杂度为O(V ∑logMi) 的01 背包问题，是很大的改进。
下面给出O(logM) 时间处理一件多重背包中物品的过程：
希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单步执行几次，或者头脑加纸笔模拟一下，以加深理解。
转化为01背包问题
用n[i]存储，可以将每种物品转化为n[i]件物品，然后用01背包方案求解。复杂度不变。如果要进行优化的话，依然用二进制思想，同上。
这样可以将时间优化为
O(V*Σlog n[i])。void MultiplePack(int weight, int cost, int amount){
if(cost * amount >= V){
CompletePack(cost, weight);
return;
}
int k = 1;
while(k < num){// num 为物品种数
ZeroOnePack(k*cost, k*weight);
amount = amount-k;
k *= 2;
}
ZeroOnePack(amount*cost, amount*weight);
} 37 void MultiplePack(int cnt, int cost) 38 { 39 if(cnt*cost >=cash)//如果第i种物品的费用总和超过背包容量，那么就是完全背包问题 40 CompletePack(cost); 41 else 42 { 43 int k = 1;//二进制拆分 44 while(k<cnt)//判断剩下的数字能不能够拆分为k 45 { 46 ZeroOnePack(cost*k); 47 cnt -=k; 48 k<<=1; 49 } 50 ZeroOnePack(cnt*cost); 51 } 52 }
3.4 可行性问题O(V N) 的算法
当问题是“每种有若干件的物品能否填满给定容量的背包”，只须考虑填满背包的可行性，不需考虑每件物品的价值时，多重背包问题同样有O(V N) 复杂度的算法。
例如，可以使用单调队列的数据结构，优化基本算法的状态转移方程，使每个状态的值可以以均摊O(1) 的时间求解。
下面介绍一种实现较为简单的O(V N) 复杂度解多重背包问题的算法。它的基本思想是这样的：设F[i; j] 表示“用了前i 种物品填满容量为j 的背包后，最多还剩下几个第i 种物品可用”，如果F[i, j] = -1 则说明这种状态不可行，若可行应满足0 ≤ F[i,j] ≤ Mi。
递推求F[i,j] 的伪代码如下：
最终F[N][0 … V ] 便是多重背包可行性问题的答案。
3.5 小结
在这一讲中，我们看到了将一个算法的复杂度由O(V ∑Mi) 改进到O(V ∑ logMi) 的过程，还知道了存在复杂度为O(V N) 的算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并将完整的程序代码写出来。
在这一讲中，我们看到了将一个算法的复杂度由O(V ∑Mi) 改进到O(V ∑ logMi) 的过程，还知道了存在复杂度为O(V N) 的算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并将完整的程序代码写出来。
http://www.voidcn.com/article/p-tinydope-pt.html
http://www.ahathinking.com/archives/109.html
对于01背包和完全背包使用一维数组实现是最简便高效的，对于多重背包，最好就是输入时进行二进制拆分，然后使用01背包，这样比基本实现和在运算时再进行拆分要简捷的多。
O（n * w *c）解法:
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int Maxn = 1005, Maxm = 1005;
int n, m, w[Maxn], v[Maxn], c[Maxn], f[Maxm + 1];
int main() {
freopen("a.in", "r", stdin);
scanf("%d", &n);
fo(i, 1, n) scanf("%d %d %d", &w[i], &v[i], &c[i]);
fo(i, 1, n) {
fd(j, Maxm, w[i])
fo(k, 1, min(c[i], j / w[i]))
f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);
}
scanf("%d", &m); printf("%d", f[m]);
}
总体积是m，每个小物品的体积是A[i] ，每个小物品的数量是B[i] 求能够放入背包内的最大物品的体积
public int backPack(int m, int[] A,int[] B ) { // write your code here int[][] P = new int[A.length+1][m+1];// P[i][j] 前i个物品放在j的空间中的最大价值 for(int i = 0;i< A.length; i++){ for(int j = m;j>=1;j--){ if(j>=A[i]){ int k = j/A[i];// 该物品最大可以放k个，然而限制条件最大是B[i] k = Math.min(k,B[i]);// 取最小值 while(k>=0){ if(j>=A[i]*k){ P[i+1][j] =Math.max(P[i+1][j], P[i][j-k*A[i]] + k*A[i]); } k--; } } else P[i+1][j] = Math.max(P[i][j],P[i+1][j]); } } return P[A.length][m]; }
转换成一维数组
public int backPack(int m, int[] A,int[] B ) { // write your code here int[] P = new int[m+1];// P[j] j的空间中的最大价值 for(int i = 0;i< A.length; i++){ for(int j = m;j>=1;j--){ if(j>=A[i]){ int k = j/A[i];// 该物品最大可以放k个，然而限制条件最大是B[i] k = Math.min(k,B[i]);// 取最小值 while(k>=0){ if(j>=A[i]*k){ P[j] =Math.max(P[j], P[j-k*A[i]] + k*A[i]); } k--; } } else P[j] = Math.max(P[j],P[j]); } } return P[m]; }
O(n*w*log c)解法：
先解释一下：n是物品个数，w是weight，即物体所占的份额，c就是物体可以有多少个。
对于当前的物品，若它能使用的个数为c，k是最大的正整数且满足2k+1<=c （ k=⌊logc2⌋ -1），y = c−(2k+1−1) 。
我们可以把原来可以用c次的物品拆分成k+2个只能用一次的物品。
前k+1个物品分别是:wi=w∗2i,vi=c∗2i,ci=1(0<=i<=k)
第k+2个物品是：w′=w∗y,v′=v∗y,c′=1
转换成了01背包问题。
这样子，我们充分利用了二进制的原理，可以刚好表示出用了次数为0-c的原物品。
对于当前的物品，若它能使用的个数为c，k是最大的正整数且满足
我们可以把原来可以用c次的物品拆分成k+2个只能用一次的物品。
前k+1个物品分别是:
第k+2个物品是：
转换成了01背包问题。
这样子，我们充分利用了二进制的原理，可以刚好表示出用了次数为0-c的原物品。
fo(i, 1, n) {
int k = log2(c[i]);
fo(z, 0, k)
fd(j, Maxm, a2[z] * w[i])
f[j] = max(f[j], f[j - a2[z] * w[i]] + a2[z] * v[i]);
int y = c[i] - a2[k];
fd(j, Maxm, y * w[i])
f[j] = max(f[j], f[j - y * w[i]] + y * v[i]);
}
问题：有个容量为V大小的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物，第i种物品最多有n[i]件可用，计算一下最多能放多少价值的货物。
对于多重背包的基本实现，与完全背包是基本一样的，不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下
1
| f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=n[i] } |
代码与完全背包的区别仅在内部循环上由
1
| for(k = 1; k <= j/weight[i]; ++k) |
变为
1
| for(k = 1; k <=n[i] && k<=j/weight[i]; ++k) |
多重背包二进制拆分实现
跟完全背包一样的道理，利用二进制的思想将n[i]件物品i拆分成若干件物品，目的是在0-n[i]中的任何数字都能用这若干件物品代换，另外，超过n[i]件的策略是不允许的。
方法是将物品i分成若干件，其中每一件物品都有一个系数，这件物品的费用和价值都是原来的费用和价值乘以这个系数，使得这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k满足n[i]-2^k+1>0的最大整数。例如，n[i]=13，就将该物品拆成系数为1、2、4、6的四件物品。分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。
int maxV[201];int weight[50]; /* 记录拆分后物体重量 */int value[50]; /* 记录拆分后物体价值 */int V, N;void main(){ int i, j; scanf("%d %d",&V, &N); int weig, val, num; int count = 0; for(i = 0; i < N; ++i) { scanf("%d %d %d",&weig,&val,&num); for(j = 1; j <= num; j <= 1) // 二进制拆分 { weight[count] = j * weig; value[count++] = j * val; num -= j; } if(num > 0) { weight[count] = num * weig; value[count++] = num * val; } } for(i = 0; i < count; ++i) // 使用01背包 { for(j = V; j >= weight[i]; --j) { int tmp = maxV[j-weight[i]] + value[i]; maxV[j] = maxV[j] > tmp ? maxV[j] : tmp; } } printf("%d",maxV[V]);}多重背包 单调队列
https://kxp555.coding.me/2017/08/27/bag4-9/
4 混合三种背包问题
4.1 问题
如果将前面1、2、3中的三种背包问题混合起来。也就是说，有的物品只可以取一
次（01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限
（多重背包）。应该怎么求解呢？
4.2 01 背包与完全背包的混合
考虑到01 背包和完全背包中给出的伪代码只有一处不同，故如果只有两类物品：
一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程
时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(V N)。伪代码如下
01背包与完全背包混合问题
由于01背包和完全背包只有第二重循环的次序不同,因此当这两类物品混合时,可以根据物品的属性采用不同的循环次序
|
|
时间复杂度是O(VN)
4.3 再加上多重背包如果再加上最多可以取有限次的多重背包式的物品，那么利用单调队列，也可以给
出均摊O(V N) 的解法。
但如果不考虑单调队列算法的话，用将每个这类物品分成O(logMi) 个01 背包的物
品的方法也已经很优了
一种简单的方法是根据物品的属性分别使用三种方法,例如
|
在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现
了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每一类背包问题
的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一
定能很快想到上面简洁的解法，对吗？
4.4 小结
有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不
论，但它在本讲中已经得到了充分的体现。本来01 背包、完全背包、多重背包都不是
什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。
但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单
的题目来解决
背包九讲（五）- 二维费用的背包问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
物品总个数的限制
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
复数域上的背包问题
另一种看待二维背包问题的思路是：将它看待成复数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复数。而常见的一维背包问题则是实数域上的背包问题。（注意：上面的话其实不严谨，因为事实上我们处理的都只是整数而已。）所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。
作为这种思想的练习，你可以尝试将（此处有连接，后补）中提到的“子集和问题”扩展到复数域（即二维），并试图用同样的复杂度解决。
小结
当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法2 二维费用的背包问题是指：对于每件物品，具有两种不同的费用， 3 选择这件物品就必须付出这两种代价，每种代价都有可付出的最大值（背包容量） 4 问怎么选择物品才能得到最大价值.费用增加了一维，那么只需要状态增加一维就可以了、 5 dp[i][j][k] 前i件物品付出两种代价为j和k的最大价值 6 dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-a[i]][k-b[i]]); 7 根据背包的思想，可将状态压缩为二维的. 8 只不过是费用增加了一维，所以01背包，完全背包，多重完全背包的思想完全
20 void zeroOnePack(int t,int v, int g) 21 { 22 int i,j; 23 for(i=T; i>=t; --i) 24 for(j=V; j>=v; --j) 25 dp[i][j] = max(dp[i][j],dp[i-t][j-v]+g); 26 } 29 int i; 30 while(scanf("%d%d%d",&T,&V,&N)!=EOF) 31 { 32 memset(dp,0,sizeof(dp)); 33 for(i=1; i<=N; ++i) 34 scanf("%d%d%d",&g[i],&t[i],&v[i]); 35 for(i=1; i<=N; ++i) 36 zeroOnePack(t[i],v[i],g[i]); 37 printf("%d\n",dp[T][V]); 38 }
但是更多的时候是隐式地给出条件，比如n个物品最多取m个，那么第二维的费用便是个数。
分组的背包问题
https://www.cnblogs.com/justPassBy/p/4279691.html2 有n件物品和一个容量为v的背包，第i件物品的费用是c[i],价值是w[i] 3 这些物品被分为若干组，每组中的物品互相冲突，即一组中只能取一件物品 4 将哪些物品装入背包使得总价值最大 5 dp[k][v] 表示前k组物品花费容量v能取到的最大值 6 dp[k][v] = max(dp[k-1][v],dp[k-1][v-c[i]]+w[i])//物品i属于第k组 7 for(i=1; i<=k; ++i) 8 for(j=v;j>=0; ++j) 9 for(所有的l属于组k) 10 if(j>=c[i]) 11 dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); 12 13 要注意for(j=v;j>=0; ++j)一定要在循环for(所有的l属于组k)之外 14 这两个循环的意义是对于每个容量j，取组k内的哪个物品更能得到最大价值 15 同样可以压缩为一维的状态 16 for(i=1; i<=k; ++i) 17 for(j=v;j>=0; ++j) 18 for(所有的l属于组k) 19 if(j>=c[i]) 20 dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
39 while(scanf("%d%d",&n,&m)!=EOF) 40 { 41 if(n==0 && m==0) break; 42 memset(dp,0,sizeof(dp)); 43 for(i=1; i<=n; ++i) 44 for(j=1; j<=m; ++j) 45 scanf("%d",&a[i][j]); 46 for(i=1; i<=n; ++i) 47 for(j=m; j>=0; --j) 48 for(k=1; k<=j; ++k) 49 { 50 dp[j] = max(dp[j],dp[j-k]+a[i][k]); 51 } 52 printf("%d\n",dp[m]); 53 }https://www.showapi.com/book/view/2011/6
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
使用一维数组的伪代码如下：
for 所有的组kfor v=V..0for 所有的i属于组kf[v]=max{f[v],f[v-c[i]]+w[i]}
注意这里的三层循环的顺序，甚至在本文的第一个beta版中我自己都写错了。“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
这里三层循环的顺序保证了每一组内的物品最多只有一个会被添加到背包中。
另外，显然可以对每组内的物品应用2.3中的优化。
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。
第七讲 有依赖的背包问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑P06中的一句话： 可以对每组中的物品应用P02中“一个简单有效的优化”。 这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件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个物品的物品组，就可以直接应用P06的算法解决问题了。
较一般的问题
更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
小结
NOIP2006的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后来我通过思考发现通过引入“物品组”和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。
我想说：失败不是什么丢人的事情，从失败中全无收获才是。
