-
2022-03-23 16:53:58
一、多重背包问题描述
有3种物品和1个背包,背包最多只能装下15公斤的物品。怎样选择物品,使得背包能装下并且得到的价值最大。物品的重量、价值和个数如下所示:
物品编号 重量 价值 件数 物品1 3公斤 2元 4件 物品2 4公斤 3元 3件 物品3 5公斤 4元 2件 二、解题思路
我们先看下0-1背包实现原理:背包问题之0-1背包算法详解_爱思考的实践者的博客-CSDN博客。
对比分析发现,多重背包与0-1背包的差别就是:对物品按种类划分,每种物品指定件数。
可以对问题进行抽象:对物品按顺序编号,物品i的重量为weight[i],价值为value[i],个数为number[i]。选取第i种物品时,已知背包当前最大承重为j,怎样装载物品,才能使得背包最大价值dp[i][j]最大?
在0-1背包状态转移方程的基础上,可以总结出多重背包的状态转移方程:
当前物品i的重量weight[i]大于背包承重j时,背包最大价值为:
dp[i][j] = dp[i-1][j]
当前物品i的重量weight[i]小于等于背包承重j时,背包最大价值为:
dp[i][j] = Math.max(dp[i-1][j - k*weight[i]] + k * value[i], dp[i-1][j])
其中,k满足条件:0 <= k < number[i] 并且 0 <= k <= j/weight[i]。
三、Java编码实现
根据上一节的状态转移方程,我们很容易就能编程解决多重背包问题。
具体实现代码为:
package com.test.packalgorithm; import com.google.common.collect.Maps; import org.apache.commons.collections4.map.MultiKeyMap; import java.util.Map; import java.util.Objects; /** * 多重背包 */ public class ManyPacksRecord { /** * 获取最大价值 * * @param N 物品个数 * @param W 背包最大承重 * @param weight 物品重量数组 * @param value 物品价值数组 * @param number 物品个数数组 * @param ij2Goods 选择的商品列表 * @return 最大价值 */ public int[][] getDp(int N, int W, int[] weight, int[] value, int[] number, MultiKeyMap<Integer, Map<Integer, Integer>> ij2Goods) { // 定义一个数组dp[i][j] i表示当前物品的序号, j表示当前书包的重量 int[][] dp = new int[N + 1][W + 1]; // 【物品种类, 背包容量】 for (int j = 0; j <= W; j++) { // 物品不存在时,最大价值肯定是0 dp[0][j] = 0; } for (int i = 1; i <= N; i++) { // 背包重量为0时,最大价值肯定是0 dp[i][0] = 0; } for (int i = 1; i <= N; i++) { // 从第1类物品开始选 for (int j = 1; j <= W; j++) { // 初始化 dp[i][j] dp[i][j] = dp[i - 1][j]; Map<Integer, Integer> preGoods = ij2Goods.get(i - 1, j); if (Objects.isNull(preGoods)) { preGoods = Maps.newHashMap(); } if (weight[i] <= j) { // 第i类物品重量 小于等于 当前承载重量,根据价值大小判断是否放入。 // 考虑物品的件数限制 int maxNumber = Math.min(number[i], j / weight[i]); for (int k = 0; k <= maxNumber; k++) { int ijkValue = dp[i - 1][j - (k * weight[i])] + (k * value[i]); dp[i][j] = Math.max(dp[i][j], ijkValue); } if (dp[i][j] > dp[i - 1][j]) { int k; for (k = 0; k <= maxNumber; k++) { int ijValue = dp[i - 1][j - (k * weight[i])] + (k * value[i]); if (dp[i][j] == ijValue) { break; } } preGoods = ij2Goods.get(i - 1, j - (k * weight[i])); if (Objects.isNull(preGoods)) { preGoods = Maps.newHashMap(); } Map<Integer, Integer> goods = Maps.newHashMap(); goods.putAll(preGoods); goods.put(i, k); ij2Goods.put(i, j, goods); } else { ij2Goods.put(i, j, preGoods); } } else { // 第i件物品重量大于当前承载重量,则不放入。 ij2Goods.put(i, j, preGoods); } } } return dp; } public static void main(String[] args) { int N = 3; // 商品种类数 int W = 15; // 背包最大承载重量 int[] w = new int[N + 1]; // 每件物品的重量,为方便理解,下标从1开始 w[1] = 3; w[2] = 4; w[3] = 5; int[] v = new int[N + 1]; // 每件物品的价值 v[1] = 2; v[2] = 3; v[3] = 4; int[] n = new int[N + 1]; // 每件物品的个数 n[1] = 4; n[2] = 3; n[3] = 2; MultiKeyMap<Integer, Map<Integer, Integer>> ij2Goods = new MultiKeyMap<>(); ManyPacksRecord obj = new ManyPacksRecord(); int[][] dp = obj.getDp(N, W, w, v, n, ij2Goods); for (int i = 0; i <= N; i++) { for (int j = 0; j <= W; j++) { System.out.printf("(%d,%d)=%-5d", i, j, dp[i][j]); } System.out.println(); } // 背包能够装入物品的最大值为 int maxValue = dp[N][W]; System.out.printf("maxValue=%d", maxValue); System.out.println(); for (int i = 1; i <= N; i++) { for (int j = 1; j <= W; j++) { System.out.printf("(%d,%d)=%-8s", i, j, ij2Goods.get(i, j).toString()); } System.out.println(); } System.out.printf("goods=%s", ij2Goods.get(N, W).toString()); } }
运行结果如下:
(0,0)=0 (0,1)=0 (0,2)=0 (0,3)=0 (0,4)=0 (0,5)=0 (0,6)=0 (0,7)=0 (0,8)=0 (0,9)=0 (0,10)=0 (0,11)=0 (0,12)=0 (0,13)=0 (0,14)=0 (0,15)=0 (1,0)=0 (1,1)=0 (1,2)=0 (1,3)=2 (1,4)=2 (1,5)=2 (1,6)=4 (1,7)=4 (1,8)=4 (1,9)=6 (1,10)=6 (1,11)=6 (1,12)=8 (1,13)=8 (1,14)=8 (1,15)=8 (2,0)=0 (2,1)=0 (2,2)=0 (2,3)=2 (2,4)=3 (2,5)=3 (2,6)=4 (2,7)=5 (2,8)=6 (2,9)=6 (2,10)=7 (2,11)=8 (2,12)=9 (2,13)=9 (2,14)=10 (2,15)=11 (3,0)=0 (3,1)=0 (3,2)=0 (3,3)=2 (3,4)=3 (3,5)=4 (3,6)=4 (3,7)=5 (3,8)=6 (3,9)=7 (3,10)=8 (3,11)=8 (3,12)=9 (3,13)=10 (3,14)=11 (3,15)=11 maxValue=11 (1,1)={} (1,2)={} (1,3)={1=1} (1,4)={1=1} (1,5)={1=1} (1,6)={1=2} (1,7)={1=2} (1,8)={1=2} (1,9)={1=3} (1,10)={1=3} (1,11)={1=3} (1,12)={1=4} (1,13)={1=4} (1,14)={1=4} (1,15)={1=4} (2,1)={} (2,2)={} (2,3)={1=1} (2,4)={2=1} (2,5)={2=1} (2,6)={1=2} (2,7)={1=1, 2=1}(2,8)={2=2} (2,9)={1=3} (2,10)={1=2, 2=1}(2,11)={1=1, 2=2}(2,12)={2=3} (2,13)={1=3, 2=1}(2,14)={1=2, 2=2}(2,15)={1=1, 2=3} (3,1)={} (3,2)={} (3,3)={1=1} (3,4)={2=1} (3,5)={3=1} (3,6)={1=2} (3,7)={1=1, 2=1}(3,8)={2=2} (3,9)={2=1, 3=1}(3,10)={3=2} (3,11)={1=1, 2=2}(3,12)={2=3} (3,13)={2=2, 3=1}(3,14)={2=1, 3=2}(3,15)={1=1, 2=3} goods={1=1, 2=3}
四、总结
多重背包状态转移方程与0-1背包状态转移方程很类似,差别只在于物品件数的限制,明确了这点,理解起来就简单了。
更多相关内容 -
贪心算法解多重背包代码
2020-05-21 15:30:31使用贪心算法解决多重背包问题(物体可拆分)的具体C++代码 -
多重背包单调队列优化问题.ppt
2018-04-07 12:24:21多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包... -
二维多重背包问题及基于遗传算法的解决方案.rar
2020-12-23 21:10:32二维多重背包问题及基于遗传算法的解决方案.rar -
背包问题(0-1背包,完全背包,多重背包知识概念详解)
2015-06-14 13:05:32背包问题(0-1背包,完全背包,多重背包知识概念详解)内含实例代码解析,详细讲解了背包的基本概念及简单运用问题 -
背包问题 01背包 完全背包 多重背包 分组背包
2022-01-22 09:26:4801背包 问题描述:给定N个物品,每个只有一件,每个物品都有相应的价值w与体积v,给定体积为M的背包,求背包所能装的最大物品价值。 分析:每个物品分为选和不选两种方案,所以一共有2的n次方种方案,方案数量特别多...01背包问题
问题描述:给定N个物品,每个只有一件,每个物品都有相应的价值w与体积v,给定体积为M的背包,求背包所能装的最大物品价值。
一般思路分析:每个物品分为选和不选两种方案,所以一共有2的n次方种方案,方案数量特别多,暴力做法不可取。
DP思路分析:用 f[ i ][ j ] 表示在前i个物品中选择方案,且选择方案总体积不超过j时的最大价值。那么 f[N][M] 就表示在前N个物品中选择,且体积不超过M的最大价值,也即题目要求的最大价值。
对 f[ i ][ j ] 可以分成两种情况分析:- 情况一: f[ i ][ j ] 中选择了第 i 个物品,那么 f[ i ][ j ] 如下表示: f[ i ][ j ] = f[ i -1 ][ j - v[ i ]] + w[ i ] 。也即说明如果我们想让 f[ i ][ j ] 是最大的,那么我们必须保证 f[ i -1 ][ j - v[ i ]] 也是最大的。
- 情况二: f[ i ][ j ] 中没有选择第 i 个物品,那么 f[ i ][ j ] 可以如下表示: f[ i ][ j ] = f[ i -1 ][ j ] 。也即说明如果我们想让 f[ i ][ j ] 是最大的,那么我们必须保证 f[ i -1 ][ j ] 是最大的。
按照上面分析我们发现,对 f[ i ][ j ] 的求解要求前面每一个 f[ x ][ y ] 都是最大的,那么我们可以先求出前面每一个过程中的最大值,进而求解出符合要求的 f[ i ][ j ] 。所以问题可以转换成:对前面每一个状态求最大值,进而得出 f[N][M] 的最大值。可以借助下面代码理解一下。
这是一种从后往前的理解方式,从结果分析出前面每一个状态的特点,再利用这一特点从前往后计算。下面的各种背包问题都可以这样理解
关键在理解 代码很简单 优化也只是对代码的一种变形核心代码如下:
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { //没有选择第i个物品 f[i][j]=f[i-1][j]; //选择了第i个物品 if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); }
滚动数组优化:(滚动数组就是个名字,就是对一个数组重复利用,将里面的数不断更新)
for(int i=1;i<=n;i++) for(int j=m;j>=v[i];j--) { f[j]=max(f[j],f[j-v[i]]+w[i]); }
完全背包问题
问题描述:给定N个物品,给的物品可以无限使用,每个物品都有相应的价值w与体积v,给定体积为M的背包,求背包所能装的最大物品价值。与01背包差别在于:01背包每种物品只能选择一次,而完全背包内的每种物品可以选择无限次。
分析:与01背包差别就在于我们需要讨论每个物品一共选择了几次,虽然物品可以无限使用,但是物品个数还是受到背包体积的限制。
朴素代码
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
第一次优化代码
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) { f[i][j]=f[i-1][j]; if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); }
第二次优化代码
for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) { f[j]=max(f[j],f[j-v[i]]+w[i]); }
#include<iostream> using namespace std; const int N=1010; int v[N],w[N],f[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); /*for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j]=f[i-1][j]; if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); }*/ /*for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);*/ for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) f[j]=max(f[j],f[j-v[i]]+w[i]); //printf("%d",f[n][m]); printf("%d",f[m]); return 0; }
多重背包问题
问题描述:第 i 种物品最多有 N 件,总共 n 种物品,求最大价值。
分析:把每一物品个数利用2进制方式拆分,最后问题变成了01背包问题。
#include<iostream> using namespace std; const int N=2010,M=130000; int v[M],w[M]; int f[N];//f[N]个数与背包总体积有关 int main() { int n,m; scanf("%d%d",&n,&m); int a,b,c; int cnt=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); int k=1; while(k<=c) { v[++cnt]=k*a; w[cnt]=k*b; c-=k; k*=2; } if(c) { v[++cnt]=c*a; w[cnt]=c*b; } } for(int i=1;i<=cnt;i++) for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); printf("%d",f[m]); return 0; }
分组背包问题
问题描述:N组物品,每组若干个,每组物品只能选择一个
分析:三层循环,枚举第 i 组物品选哪一个
代码
for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=s[i];k++) { if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); }
#include<iostream> using namespace std; const int N=110; int v[N][N],w[N][N],f[N],s[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&s[i]); for(int j=1;j<=s[i];j++) scanf("%d%d",&v[i][j],&w[i][j]); } for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=s[i];k++) { if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } printf("%d",f[m]); return 0; }
总结
01背包:
f[j]=max(f[j],f[j-v[i]]+w[i]);//j从大到小
完全背包:f[j]=max(f[j],f[j-v[i]]+w[i]);//j从小到大
多重背包:f[j]=max(f[j],f[j-v[i]]+w[i]);//j从大到小
分组背包:f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);//j从大到小
只有完全背包是从小到大
-
多重背包代码资源.cpp
2020-03-26 15:02:55本代码来自于我的文章,如有特殊需求可私信本人。程序错误可在我的文章下面提出问题,详细讲解请看我的文章,请各位大佬支持支持 -
多重背包
2021-03-06 01:25:51多重背包问题Ⅰ有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。数据范围:0<...多重背包问题Ⅰ
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
数据范围:
0< N , V ≤100
0< vi , wi , si ≤100
//朴素版多重背包问题≈朴素版完全背包问题,只不过加了物品数量的限定条件
#include
#include
using namespace std;
const int N=110;
int n,m;
int s[N],w[N],v[N];
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<
return 0;
}
多重背包问题Ⅱ
数据范围:
0< N ≤1000
0< V ≤2000
0< vi , wi , si ≤2000
最主要的思想是二进制优化,把问题转化为01背包问题
int k=1;
while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//如果s[i]没用连续的二进制打包完
if(s>0)
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
n=cnt;//这是新的物品数量
#include
#include
#include
using namespace std;
const int N=12010;
int dp[N];
int v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
//对每个s[i]二进制打包
int k=1;
while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//如果s[i]没用连续的二进制打包完
if(s>0)
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;//这是新的物品数量
//因为经过上述操作后,每个物品的数量都来变成了1,于是转变成01背包问题,O(nvlogs)
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<
return 0;
}
-
【动态规划】多重背包问题
2021-04-13 13:54:02说明前面已经介绍完了01背包和完全背包,今天介绍最后一种背包问题——多重背包。这个背包,听起来就很麻烦的样子。别慌,只要你理解了前面的两种背包问题,拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和...说明
前面已经介绍完了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) = max{ks(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) = max{ks(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) = max{ks(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) = max{ks(t), ks(t - Vi) + Pi}
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[] 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++){
// 考虑第m个物品
// 分两种情况
// 1: M[m] * V[m] > T 则可以当做完全背包问题来处理
if (M[m] * V[m] >= T) {
for (int n = V[m]; n <= t ; n++) {
newResults[n] = Math.max(newResults[n], newResults[n - V[m]] + P[m]);
}
} else {
// 2: M[m] * V[m] < T 则需要在 newResults[n-V[m]*k] + P[m] * k 中找到最大值,0 <= k <= M[m]
for (int n = V[m]; n <= t ; n++) {
int k = 1;
while (k < M[m] && n > V[m] * k ){
newResults[n] = Math.max(newResults[n], newResults[n - V[m] * k] + P[m] * k);
k++;
}
}
}
// 可以在这里输出中间结果
System.out.println(JSON.toJSONString(newResults));
}
return newResults[newResults.length - 1];
}
}
输出如下:
[0,0,0,0,2,2,2,4,4,4,6,6,6,8,8,8]
[0,0,0,0,2,3,3,4,5,6,6,7,8,9,9,10]
[0,0,0,0,2,3,4,4,5,6,7,8,8,9,10,11]
11
这里有一个较大的不同点,在第二层循环中,需要分两种情况考虑,如果 M[m] * V[m] >= T ,那么第m个物品就可以当做完全背包问题来考虑,而如果 M[m] * V[m] < T,则每次选择时,需要从 newResults[n-V[m]*k] + P[m] * k(0 <= k <= M[m])中找到最大值。
代码很简单,但要理解却并不容易,为了加深理解,再画一张图:
多重背包问题同样也可以转化成01背包问题来求解,因为第i件物品最多选 M[i] 件,于是可以把第i种物品转化为M[i]件体积和价值相同的物品,然后再来求解这个01背包问题。
总结
多重背包问题跟完全背包简直如出一辙,仅仅是比完全背包多一个限制条件而已,如果你回过头去看看前一篇文章,就会发现这篇文章简直就是抄袭。。
关于多重背包问题的解析到此就结束了,三个经典的背包问题到这里就告一段落了。
如果有疑问或者有什么想法,也欢迎关注我进行留言交流:
-
AcWing 4. 多重背包问题(多重背包 朴素版)
2022-02-17 19:09:08对于每一个物品我们在选择的时候是有限制的,所以我们进行选择的时候需要枚举一下可以选择的情况,注意的是我们在循环枚举物品的次数以及当前的背包容量的时候,背包容量一定要在物品的次数的上面,这样进行递推才是... -
贪心算法 多重背包
2013-06-15 23:38:40用贪心算法解决多重背包问题的C++解决方法 -
多重背包单调队列优化问题.pdf
2020-06-09 01:49:32多重背包单调队列优化问题.pdf -
01背包、完全背包、多重背包、分组背包问题,一文读懂
2022-04-12 15:07:12背包问题是一种组合优化的 NP 完全问题:有 N 个物品和容量为 W 的背包,每个物品都有 自己的体积 w 和价值 v,求拿哪些物品可以使得背包所装下物品的总价值最大。 0-1背包 有N件物品和一个最多能背重量为W 的背包。... -
AcWing 4. 多重背包问题 I (多重背包模板题 两种方法)
2022-04-05 15:13:11有NN种物品和一个容量是VV的背包。 第ii种物品最多有sisi件,每件体积是vivi,价值是wiwi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个... -
01-背包、完全背包、多重背包及其相关应用
2021-03-18 11:36:25本文介绍了背包问题系列,主要包括:【1】 01-背包及其应用【2】完全背包及其应用【3】多重背包【1】01-背包及其应用:1.1、01-背包问题描述:有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 ... -
多重背包的各种优化
2022-03-30 09:15:46多重背包问题 I为例,贴一个代码: #include <bits/stdc++.h> using namespace std; int w[105], v[105], num[105], dp[105]; signed main(){ int n, m; cin >> n >> m; for(int -
背包问题(01背包、完全背包、多重背包)
2021-06-08 22:02:00文章目录1、01背包问题2、完全背包问题3、多重背包问题 1、01背包问题 问题描述: 给定物体数量N,以及背包能够装下的最大重量V,对于物品i, 其重量为 weight[i],价值为value[i]。每种物品最多只能拿一次,求在不... -
多重背包问题大全(超详细)
2021-03-23 17:22:50首先多重背包问题可以转换为01背包来解决,关键就是如何转换! 我们先来一种最基本的解法。 朴素解法 基本思想:比如第i件物品有s个,我可以把相同种类的物品的进行合并,比如我拿出两件合并出一个新的物品,我拿出三件... -
多重背包问题和“二进制拆分”
2022-03-24 09:50:42多重背包、二进制拆分 -
动态规划 多重背包问题
2022-02-26 16:43:58多重背包问题 I 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 ... -
动态规划之背包问题(01背包问题、完全背包问题、多重背包问题 I、多重背包问题 II 、分组背包问题)
2022-03-30 16:58:59动态规划之背包问题(01背包问题、完全背包问题、多重背包问题 I、多重背包问题 II 、分组背包问题) -
多重背包问题
2020-12-31 03:54:17题目有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。基本算法这题目和完全背包问题很类似... -
01,完全,多重背包,背包问题(Python)
2020-04-27 13:43:45文章目录概述01-背包问题题目描述:分析原分析扩展分析代码完全背包题目描述分析代码原分析代码二维dp转一维dp代码省略取物品次数k的等价转换代码多重背包 概述 01-背包问题 完全背包问题 多重背包问题 多重背包... -
动态规划:多重背包问题
2022-04-22 14:38:24多重背包问题I 一、状态表示 f[i][j],表示从前i个物品当中选,总体积不超过j的选法,求解的是最大值 二、集合划分 f[i][j]根据第i见物品选择的数量进行划分,f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2 * w.... ... -
动态规划 多重背包问题(二进制优化)
2022-02-27 16:54:09多重背包问题 II 有 NNN 种物品和一个容量是 VVV 的背包。 第 iii 种物品最多有 sis_isi 件,每件体积是 viv_ivi,价值是 wiw_iwi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大... -
背包问题(多重背包&混合背包)
2021-08-21 08:44:26背包问题(多重背包&混合背包) 1.多重背包 多重背包问题的思路跟完全背包的思路非常类似,只是k的取值是有限制的,因为每件物品的数量是有限制的,状态转移方程为: dp[i][v] = max{dp[i - 1][v - k * c[i]] +... -
多重背包问题(来源:背包九讲)
2021-03-07 23:02:26问题:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。基本算法:这题目和完全背包问题很... -
01背包输出路径、完全背包、多重背包
2022-02-26 20:14:12多重背包问题Ⅰ多重背包问题Ⅱ 01 Knapsack(输出路径- >选的物品) #include <iostream> #include <stack> #include <string.h> using namespace std; const int N=105; int w[N]; int v[N]; ... -
【算法】多重背包问题
2021-03-24 15:09:441 背包问题 1.1 题目描述 有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,能够得到的最大价值是多少?(对于每个物品不... -
多重背包的二进制优化
2022-02-26 23:35:04多重背包的二进制优化 多重背包 比较朴素的多重背包(空间使用了一维数组优化) public int multiBag( int[] weight , int[] value , int[] num , int capacity ) { int[] dp = new int[capacity+1]; int len = ...