【背包问题】多重背包问题
程序员文章站
2024-03-17 22:04:04
...
一、多重背包问题
1.1 题目
有 N N N 种物品和一个容量为 V V V 的背包。第 i i i 种物品最多有 M i M_i Mi 件可用，每件耗费的空间是 C i C_i Ci，价值是 W i W_i Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
1.2 思路
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。
因为对于第
i
i
i 种物品有
M
i
+
1
M_i + 1
Mi+1 种策略：取 0 件，取 1 件……取
M
i
M_i
Mi 件。令
F
[
i
,
v
]
F[i, v]
F[i,v]表示前
i
i
i 种物品恰放入一个容量为
v
v
v 的背包的最大价值，则有状态转移方程：
F
[
i
,
v
]
=
m
a
x
{
F
[
i
−
1
,
v
−
k
∗
C
i
]
+
k
∗
W
i
∣
0
⩽
k
⩽
M
i
}
F[i,v]=max\{F[i-1,v-k*C_i]+k*W_i|0\leqslant k \leqslant M_i\}
F[i,v]=max{F[i−1,v−k∗Ci]+k∗Wi∣0⩽k⩽Mi}
复杂度是
O
(
V
Σ
M
i
)
O(V ΣM_i)
O(VΣMi)。
/**
* 第三类背包：多重背包
*
* @param args
*/
public static int manyPack(int V,int N,int[] weight,int[] value,int[] num){
//初始化动态规划数组
int[][] dp = new int[N+1][V+1];
//为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
for(int i=1;i<N+1;i++){
for(int j=1;j<V+1;j++){
//如果第i件物品的重量大于背包容量j,则不装入背包
//由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
if(weight[i-1] > j)
dp[i][j] = dp[i-1][j];
else{
//考虑物品的件数限制
int maxV = Math.min(num[i-1],j/weight[i-1]);
/*for(int k=0;k<maxV+1;k++){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);
}*/
for(int k=0;k<maxV+1;k++){
dp[i][j] = dp[i][j]>Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]) ? dp[i][j]:Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);
}
}
}
}
/*//则容量为V的背包能够装入物品的最大值为
int maxValue = dp[N][V];
int j=V;
String numStr="";
for(int i=N;i>0;i--){
//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
while(dp[i][j]>dp[i-1][j]){
numStr = i+" "+numStr;
j=j-weight[i-1];
}
if(j==0)
break;
}*/
return dp[N][V];
}