这是为了验证公式的正确性，这里省略了

6.实现代码

根据上面的分析，很容易写出以下实现代码

public static int bagComplete(int[] weight, int[] value, int capability){
        int[][] dp = new int[weight.length][capability + 1];
        //初始化
        for(int j = weight[0]; j <= capability; j++){
            dp[0][j] = value[0] * (j / weight[0]);
        }

        //先遍历i，再遍历j
        for(int i = 1; i < weight.length; i++){
            for(int j = 0; j <= capability; j++){
                if(j < weight[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                }
            }
        }

        //先遍历j，再遍历i
        // for(int j = 0; j <= capability; j++){
        //     for(int i = 1; i < weight.length; i++){
        //         if(j < weight[i]){
        //             dp[i][j] = dp[i - 1][j];
        //         }else{
        //             dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
        //         }
        //     }
        // }

        return dp[weight.length][capability];
    }

三.空间优化

类似于01背包问题，上面的代码中，我们发现时间复杂度已经达到最低O(vn)，(v为背包容量，n为物品数量)，但空间复杂度O(vn)还可以优化。

1.思路

与01背包问题相同，我的思路也是去掉i这一维度，改成通过控制遍历顺序，达到和二维数组相同的效果。

2.递推顺序

通过与01背包类似的分析，我们得出的结论应该是只能先遍历i再遍历j，j顺序遍历。但是，由于还可以由其他公式推出正确结果，我们会发现先遍历j再遍历i，j顺序遍历也是能得出正确结果的。原因分析如下：

先遍历j再遍历i，j顺序遍历的分析

我直接从一维数组的dp出发来思考递推关系式。dp[j]表示背包容量为j时，考虑所有物品情况下的最大价值。可以想到，类似于爬楼梯的思路，想要达成容量为j的最大价值，最后一个放入的物品只能是第0种，第1种，...，第n种，然后取这些情况的最大值就行

假设最后放入的是第i种

此时想要背包物品价值最大，我们只要让背包容量为j - w[i]的时候物品价值最大，然后加上第i个的价值，即dp[j - w[i]] + v[i]

所以，我们可以得出dp[j] = max(dp[j - w[i]] + v[i])，(i从0取到n或者从n取到0)，显然j也必须从小取到大，然后转换成代码，形式上就是先遍历j再遍历i的代码。

ps：01背包问题不能如此思考的原因

在01背包问题的情景下，每一种物品只有一个，而在算dp[j - w[i]]时，根据定义，在达成容量为j - w[i]的最大价值时，我们有可能已经把第i号物品使用了，所以这个公式在01背包中是不成立的

3.初始化

与01背包相同，这里也有两种初始化方法

1. 方法1

   类似二维数组的初始化方式，将dp[j]中的每一个数初始化为dp[0][j]的值，i从1开始遍历，具体代码见后面的实现代码部分

2. 方法2

   初始化为"i = -1"的那一行，定义为任何物品都不装的情况下，容量为j的背包的最大价值，显然最大价值为0，此时i从0开始遍历即可

4.实现代码

1. 使用方法1初始化

   public static int bagComplete1(int[] weight, int[] value, int capability){
           int[] dp = new int[capability + 1];
   
           //初始化法1
           for(int j = weight[0]; j <= capability; j++){
               dp[j] = value[0] * (j / weight[0]);
           }
   
           //先遍历i，再遍历j
           for(int i = 1; i < weight.length; i++){
               for(int j = weight[i]; j <= capability; j++){
                   dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
               }
           }
   
           //先遍历j，再遍历i
           // for(int j = 0; j <= capability; j++){
           //     for(int i = 1; i < weight.length; i++){
           //         if(j >= weight[i]){
           //             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
           //         }
           //     }
           // }
           return dp[capability];
       }
   

2. 使用方法2初始化

   public static int bagComplete2(int[] weight, int[] value, int capability){
           int[] dp = new int[capability + 1];
   
           //初始化法2
           //初始化dp[-1][j],即在没有物品的情况下，不同背包容量的最大价值，显然都是0
   
           //先遍历i，再遍历j
           for(int i = 0; i < weight.length; i++){
               for(int j = weight[i]; j <= capability; j++){
                   dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
               }
           }
   
           //先遍历j，再遍历i
           // for(int j = 0; j <= capability; j++){
           //     for(int i = 0; i < weight.length; i++){
           //         if(j >= weight[i]){
           //             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
           //         }
           //     }
           // }
           return dp[capability];
       }