辅助理解01背包问题和完全背包问题的优化思想
1、先上代码（Java）
import java.util.Arrays;
public class CompleteBackpack {
private int[] weight, value; //重量，价值
private static int cap[];//cap[i]表示可用重量为i时的最大价值
private int C;//最大容量
//01背包
public int knapsack01() {
int length = weight.length;
if (length == 0) return 0;
for (int i = 1; i <= length; i++) {
for (int j = C; j >=weight[i-1]; j--) { //自顶向下
cap[j]=Math.max(cap[j], cap[j-weight[i-1]]+value[i-1]);
}
}
return cap[C];
}
//完全背包
public int completeknapsack() {
int length = weight.length;
if (length == 0) return 0;
for (int i = 1; i <= length; i++) {
for (int j = weight[i-1]; j <= C; j++) { //自底向上
cap[j] = Math.max(cap[j], cap[j - weight[i-1]]+ value[i-1]);
}
}
return cap[C];
}
public void init(int[] value, int[] weight,int c) {
this.weight=weight;
this.value = value;
this.C = c;
cap = new int[c+1];
Arrays.fill(cap,0);
}
public static void main(String[] args) {
int[] value= {8,5,4,3};
int[] weight= {5,4,3,2};
int c = 10;
CompleteBackpack knapsack = new CompleteBackpack();
knapsack.init(value, weight, c);
System.out.println(knapsack.knapsack01());
System.out.println(knapsack.completeknapsack());
}
}
2、完全背包
先分析完全背包是我认为优化后的完全背包比01背包容易理解
完全背包和01背包的这种优化思想是从建表的解法上改进了：表格中下一行的值只跟上一行有关，需要了解演变过程的同学，可以查看这篇文章，下面结合图来分析该优化的思想
优化的解法中，使用一维数组（ private static int cap[ ]）来做存储，其表示的含义是：cap[i]表示可用重量为i时的最大价值，理解这点很重要
下面结合上面代码来介绍
-
第0层，虚拟的，为第1层做铺垫，全部都初试为0
-
第1层，即i=1时，对于第二重for循环，j的起点为第1件物品的重量，这里很明显，如果可用重量j低于这件物品的重量，肯定是无法放入背包中。然后在可用重量j从5到9的过程中，最大价值都是8，以j=5时举例，在上一层，即第0层中，可用重量为j时，最大价值为0，即如果不将第1件物品放入背包，那么此时最大价值为0，记为价值A，而如果将第1件物品放入背包中，那么此时最大价值为cap[5 - weight[0]]+ value[0]，即不放入第1件物品时的最大价值+第1件物品的价值，记为价值B，比较A和B，取最大值作为此时可用重量的最大价值。在这里可以看到，当可用重量j为5时，不放入第1件物品的最大价值为cap[0],随着可用重量j的不断增大，直到9，最大价值取得的方式都是0+8，而当j到10，背包中可以容纳两个 第1件物品，，此时最大价值变为
cap[10 - weight[0]]+ value[0]=cap[5]+8=8+8=16
这里用到了可用重量为5时的最大价值，即实现了物品的重复使用
此时，内循环完成，得到了当前能够获得的最大价值。 -
第2层，下面，第2件物品入场了。
依据上面的思路，第2件物品的重量为4，那么可用重量j从4开始，可用得到cap[4]=5，然后继续往下遍历，当可用重量j变为8时，cap[8-weight[1]]+value[1]=5+8=13，与上一层可用重量为8时的最大价值cap[8]=8相比较，更新可用重量为8时的最大价值为13，继续遍历，最后得到如下： -
第3层，得到的结果为
5.第4层，得到的结果为
3、 01背包
分析完完全背包，再来看01背包问题就简单了，同样，优化的解法中，使用一维数组（ private static int cap[ ]）来做存储，其表示的含义是：cap[i]表示可用重量为i时的最大价值
01背包与完全背包最大的不同，就是物品不能重复选择，一件物品只能选择一次，所以在更新cap[i]时，就不能像完全背包那样，那么要如何实现在新一轮更新中，即要使用上一轮的结果，又要使得这轮前面更新的结果不会对后面的更新产生影响（即同一个物品重复使用问题）？
答案就是跟完全背包反着来，因为完全的内循环是自底向上，那么反过来就是自顶向下。
- 第0层，同样，直接初始化为0，为第1层做铺垫
- 第1层，可用重量j从10开始，逐步减小，直到等于第1件物品的重量（再减小的话，就放不进背包了），以可用重量j=10来举例，上层cap[10]=0，即不放第1件物品的情况，如果要放入的话，那么上一层的最大价值应该是cap[10-5]，放入后，总的最大价值为cap[10-5]+value[0]=0+8=8，比较放跟不放的情况，取最大值，得cap[10]=8。接下来是可用重量j=9，上层cap[9]=0，这是不放第1件物品的情况，如果放入就变成了cap[9-5]+value[0]=8，可得cap[9]=8。同理，可以得到下图的结果，从这个过程中，我们可以发现，在这一轮的更新过程中（或者说一次内循环过程），前面的更新不会影响后面的更新（这里的前面、后面不是指数组cap的前后，而是更新过程的前后，两者是相反的，cap中靠前的元素，是最后更新的），这样一件物品只会被放入一次（是否放入是从cap的值来体现的，完全背包也是一样，因为前面的更新了后面，实现了物品价值的累加）。
- 第2层，结果如下
- 第3层，结果如下
- 第4层，结果如下
本文地址：https://blog.csdn.net/weixin_44219085/article/details/107687922