在上一篇文章中我们总结了一下01背包问题，接下来我们介绍背包家族中的另外一个重要成员完全背包。
完全背包的例子
上一次小偷得手后，尝到了甜头，打算接着作案。这一次他来到了另外一个人的家里，与上次不同的是，这次主人家每件东西都有无数件（当然这个条件是我们假设的），小偷的包的容量是有限的，问如何选择才能使得所获得的利益是最大的？
理论分析
假设第i件物品的体积为v[i],价值为w[i]。完全背包问题可以转换为01背包进行求解，状态转移方程为dp[i][v]=max{dp[i-1][v],dp[i-kv[i]+kw[i] (k>=1&k<=(v/v[i]))},这种思路是基于01背包问题的解决办法，比较容易理解，我们在这里就不在赘述。另外一种思路就是dp[i][v]=max{dp[i-1][v],dp[i][i-v[i]]+w[i]}。dp[i][v]表示当背包容量为v时，尽可能的多添加i种物品所能获得的最大收益。它与之前i的添加情况有关。与01背包问题一样，我们也可以对空间复杂度进行优化，优化的状态转移方程为dp[v]=max{dp[v],dp[v-v[i]]+w[i]},有没有一种很熟悉的感觉，是的，这就是01背包中优化后的表达式。但是与01背包不同的是我们的内循环是从v->v[i]的，01背包中是从v[i]->v的。主要原因就是01中的i件物品只有一件，只有选或者不选两种选择，而完全背包则不同。
具体的Java代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class {
public static void main(String[] args){
int result=getMaxValue(5,new int[]{3,2,2},new int[]{5,10,20});
System.out.println(result);
}
public static int getMaxValue(int cap,int[] v,int[] w){
int[] dp=new int[cap+1];
for(int i=0;i<cap+1;i++){
dp[i]=0;
}
for(int i=1;i<=v.length;i++){
for(int j=v[i-1];j<cap+1;j++){
dp[j]=Math.max(dp[j],dp[j-v[i-1]]+w[i-1]);
}
}
return dp[cap];
}
}
|
运行结果为：
1
2
|
40
Process finished with exit code 0
|
判断选择了哪些物品
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
for(int i=1;i<=v.length;i++){
for(int j=v[i-1];j<cap+1;j++){
dp[j]=Math.max(dp[j],dp[j-v[i-1]]+w[i-1]);
if(dp[j]==dp[j-v[i-1]]+w[i-1]){
path[i][j]=1;
}
}
}
int i=v.length;
int j=cap;
while(i>0&&j>0){
if(path[i][j]==1){
System.out.println(i);
j=j-v[i-1];
}
else{
i--;
}
}
|
参考文献：
完全背包详解（最优方法）
“完全背包”详解及实现（包含背包具体物品的求解）
背包九讲
近期评论