关键词：
说明
前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。
这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。
如果没有看过前两篇01背包和完全背包的文章，强烈建议先阅读一下，因为本文跟前两篇文章关联性很强。
多重背包
有N种物品和一个容量为T的背包，第i种物品最多有M[i]件可用，价值为P[i]，体积为V[i]，求解：选哪些物品放入背包，可以使得这些物品的价值最大，并且体积总和不超过背包容量。
对比一下完全背包，其实只是多了一个限制条件，完全背包问题中，物品可以选择任意多件，只要你装得下，装多少件都行。
但多重背包就不一样了，每种物品都有指定的数量限制，所以不是你想装，就能一直装的。
举个栗子：有A、B、C三种物品，相应的数量、价格和占用空间如下图：
跟完全背包一样，贪心算法在这里也不适用，我就不重复说明了，大家可以回到上一篇中看看说明。
递归法
还是用之前的套路，我们先来用递归把这个问题解决一次。
用ks(i,t)表示前i种物品放入一个容量为t的背包获得的最大价值，那么对于第i种物品，我们有k种选择，0 <= k <= M[i] && 0 <= k * V[i] <= t，即可以选择0、1、2...M[i]个第i种物品，所以递推表达式为：
ks(i,t) = maxks(i-1, t - V[i] * k) + P[i] * k; （0 <= k <= M[i] && 0 <= k * V[i] <= t）同时，ks(0,t)=0;ks(i,0)=0;
对比一下完全背包的递推关系式：
ks(i,t) = maxks(i-1, t - V[i] * k) + P[i] * k; （0 <= k * V[i] <= t）简直一毛一样，只是k多了一个限制条件而已。
使用上面的栗子，我们可以先写出递归解法：
public static class MultiKnapsack
private static int[] P=0,2,3,4;
private static int[] V=0,3,4,5;
private static int[] M=0,4,3,2;
private static int T = 15;
@Test
public void soleve1()
int result = ks(P.length - 1,T);
System.out.println("最大价值为：" + result);
private int ks(int i, int t)
int result = 0;
if (i == 0 || t == 0)
// 初始条件
result = 0;
else if(V[i] > t)
// 装不下该珠宝
result = ks(i-1, t);
else
// 可以装下
// 取k个物品i，取其中使得总价值最大的k
for (int k = 0; k <= M[i] && k * V[i] <= t; k++)
int tmp2 = ks(i-1, t - V[i] * k) + P[i] * k;
if (tmp2 > result)
result = tmp2;
return result;
同样，这里的数组P/V/M分别添加了一个元素0，是为了减少越界判断而做的简单处理，运行如下：
最大价值为：11对比一下完全背包中的递归解法：
private int ks(int i, int t)
int result = 0;
if (i == 0 || t == 0)
// 初始条件
result = 0;
else if(V[i] > t)
// 装不下该珠宝
result = ks(i-1, t);
else
// 可以装下
// 取k个物品i，取其中使得总价值最大的k
for (int k = 0; k * V[i] <= t; k++)
int tmp2 = ks(i-1, t - V[i] * k) + P[i] * k;
if (tmp2 > result)
result = tmp2;
return result;
仅仅多了一个判断条件而已，所以只要弄懂了完全背包，多重背包就不值一提了。
最优化原理和无后效性的证明跟多重背包基本一致，所以就不重复证明了。
动态规划
参考完全背包的动态规划解法，就很容易写出多重背包的动态规划解法。
自上而下记忆法
ks(i,t) = maxks(i-1, t - V[i] * k) + P[i] * k; （0 <= k <= M[i] && 0 <= k * V[i] <= t）public static class MultiKnapsack
private static int[] P=0,2,3,4;
private static int[] V=0,3,4,5;
private static int[] M=0,4,3,2;
private static int T = 15;
private Integer[][] results = new Integer[P.length + 1][T + 1];
@Test
public void solve2()
int result = ks2(P.length - 1,T);
System.out.println("最大价值为：" + result);
private int ks2(int i, int t)
// 如果该结果已经被计算，那么直接返回
if (results[i][t] != null) return results[i][t];
int result = 0;
if (i == 0 || t == 0)
// 初始条件
result = 0;
else if(V[i] > t)
// 装不下该珠宝
result = ks2(i-1, t);
else
// 可以装下
// 取k个物品，取其中使得价值最大的
for (int k = 0; k <= M[i] && k * V[i] <= t; k++)
int tmp2 = ks2(i-1, t - V[i] * k) + P[i] * k;
if (tmp2 > result)
result = tmp2;
results[i][t] = result;
return result;
这里其实只是照葫芦画瓢。
自下而上填表法
同样也可以使用填表法来解决，此时需要将数组P、V、M额外添加的元素0去掉。
除了k的限制不一样之外，其他地方跟完全背包的解法完全一致：
public static class MultiKnapsack
private static int[] P=2,3,4;
private static int[] V=3,4,5;
private static int[] M=4,3,2;
private static int T = 15;
private int[][] dp = new int[P.length + 1][T + 1];
@Test
public void solve3()
for (int i = 0; i < P.length; i++)
for (int j = 0; j <= T; j++)
for (int k = 0; k <= M[i] && k * V[i] <= j; k++)
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j-k * V[i]] + k * P[i]);
System.out.println("最大价值为：" + dp[P.length][T]);
跟01背包问题一样，完全背包的空间复杂度也可以进行优化，具体思路这里就不重复介绍了，可以翻看前面的01背包问题优化篇。
优化后的状态转移方程为：
ks(t) = maxks(t), ks(t - Vi) + Pipublic static class MultiKnapsack
private static int[] P=2,3,4;
private static int[] V=3,4,5;
private static int[] M=4,3,2;
private static int T = 15;
private int[] newResults = new int[T + 1];
@Test
public void resolve4()
int result = ksp(P.length,T);
System.out.println(result);
private int ksp(int i, int t)
// 开始填表
for (int m = 0; m < i; m++)
for (int n = V[m]; n <= t ; n++)
if (n >= V[m] * (M[m] + 1))
newResults[n] = newResults[n - 1];
else
newResults[n] = Math.max(newResults[n] , newResults[n - V[m]] + P[m]);
// 可以在这里输出中间结果
System.out.println(JSON.toJSONString(newResults));
return newResults[newResults.length - 1];
输出如下：
[0,0,0,2,2,2,4,4,4,6,6,6,8,8,8,8]
[0,0,0,2,3,3,4,5,6,6,7,8,9,9,10,11]
[0,0,0,2,3,4,4,5,6,7,8,8,9,10,11,11]
11这里的优化多了一个限制条件，跟完全背包相比，唯一的区别在这里：
if (n >= V[m] * (M[m] + 1))
newResults[n] = newResults[n - 1];
else
newResults[n] = Math.max(newResults[n] , newResults[n - V[m]] + P[m]);
代码很简单，但要理解却并不容易，为了加深理解，再画一张图：
多重背包问题同样也可以转化成01背包问题来求解，因为第i件物品最多选 M[i] 件，于是可以把第i种物品转化为M[i]件体积和价值相同的物品，然后再来求解这个01背包问题。
总结
多重背包问题跟完全背包简直如出一辙，仅仅是比完全背包多一个限制条件而已，如果你回过头去看看前一篇文章，就会发现这篇文章简直就是抄袭。。
关于多重背包问题的解析到此就结束了，三个经典的背包问题到这里就告一段落了。
如果有疑问或者有什么想法，也欢迎关注我的公众号进行留言交流：
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
动态规划——背包问题(代码片段)
...析最基础的方法是枚举，但时间复杂度为O(22)O(2^2)O(22)动态规划的可以将时间复杂度降为O(nm)O(nm 查看详情
动态规划算法-07背包问题进阶(代码片段)
简介我们在本专栏之前的文章介绍了基础的01背包问题及其解题思路，本文我们将讲述其拓展题型，也就是完全背包问题和多重背包问题。01背包问题首先，我们先来简单回顾一下经典的01背包问题，关于01背包的... 查看详情
动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情
acm-动态规划小白入门：背包/线性/区间/计数/数位统计/状压/树形/记忆化dp(代码片段)
动态规划-AcWing基础课一、背包问题1、01背包：每件物品最多只能选一次2、完全背包:每件物品可以选任意次3、多重背包（朴素版）：限定每件物品选择次数的上限4、多重背包（二进制优化版）：限定... 查看详情
动态规划-第二节：动态规划之背包类型问题(代码片段)
文章目录一：01背包问题（1）题目描述（2）解题思路（3）完整代码二：分割等和子集（01背包变形）（1）题目描述（2）解题思路（3）完整代码三：完全背包问题&... 查看详情
动态规划—多重背包(代码片段)
多重背包类似于完全背包，只是每个物品可以选取的数目已经告诉我们了，做题的思路和完全背包几乎一样。对于二维数组的做法，我们只要对k多做一个k<=c[i]的限制即可，c[i]是第i件物品最多能选用的次数。看题： 急！... 查看详情
动态规划-背包问题(代码片段)
...为“无界背包或完全背包”问题。一、0-1背包问题可以用动态规划来解决背包问题。以0-1背 查看详情
动态规划解决背包问题(代码片段)
...音响价格3000或者装吉他和电脑价值3500这道题我们可以用动态规划算法来解决动态规划算法介绍：1.动态规划算法的核心思想是&#x 查看详情
0-1背包问题_动态规划(代码片段)
...sp;普通背包问题可以用贪心来解决，而0-1背包问题只能靠动态规划来做，而且在我们平时的做题中经常会遇到0-1背包问题的变形，所以有必要牢牢掌握0-1背包问题的思想和解题思路。根据下面的图更可以找到应该选那些背包下面... 查看详情
动态规划-多重背包(取的次数有限制)(代码片段)
#include<stdio.h>#include<algorithm>usingnamespacestd;intv[6002],w[6002],s[6002];intf[6002];intn,m;//多重背包intmain()scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&s[i]);for(inti=1;i<=n;i++)for(intj=m;j>=0;j--)for(intk=0;k<=s[i];k... 查看详情
动态规划-01背包问题(代码片段)
算法思想：动态规划实际问题：01背包问题编写语言：Java问题描述给定n种物品和一个背包，物品i的重量为wi，其价值是vi，背包的容量为c，问应如何向背包装入物品，使得背包中的物品价值最大。每个物品拿取或者不拿两种选... 查看详情
#动态规划0-1背包问题思路概述(代码片段)
01背包问题是动态规划中的经典问题。本篇文章主题：分析与优化最基本的01背包问题，对此类问题解题有一个基本的解题模板。 问题概述：有一个背包，他的容量为C（Capacity）。现在有n种不同的物品编号分别为0、1....n... 查看详情
acm-动态规划小白入门(代码片段)
动态规划-AcWing基础课一、背包问题1、01背包：每件物品最多只能选一次2、完全背包:每件物品可以选任意次3、多重背包（朴素版）：限定每件物品选择次数的上限4、多重背包（二进制优化版）：限定... 查看详情
动态规划之背包问题(代码片段)
...问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态+选择，也没啥特别之处嘛。今天就来说一下背包问题吧... 查看详情
算法笔记万物皆可dp——动态规划常见类型heroding的算法之路(代码片段)
万物皆可DP前言1.动态规划解题思路1.1解题思路1.2问题特点2.背包问题2.101背包问题2.2完全背包问题2.3多重背包问题3.字符串问题3.1最长公共子序列3.2分割回文串II4.股票问题5.总结前言如果说搜索算法占据了机试算法题的半壁江山&#... 查看详情