题解 | #01背包#_牛客博客

描述
已知一个背包最多能容纳物体的体积为V
现有n个物品第i个物品的体积为 $图片说明$ , 第i个物品的重量为 $图片说明$
求当前背包最多能装多大重量的物品
示例

输入：
10,2,[[1,3],[10,4]]
返回值：
4
说明：
第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

方法一：动态规划
这道题是经典的用动态规划可以解决的题
• 首先我们要明确两个问题，状态和选择，状态有两个，分别是是可选择的物品和背包的容量，选择也很容易想到，就是装进背包与不装进背包

• 其次，我们要明确 $dp$ 数组的含义，这里我们需要定义一个二维 $dp$ 数组 $dp[i][v]$ , $i$ 表示当前装进背包的物品数量， $v$ 表示当前背包的容量，而 $dp[i][v]$ 的值就代表这种情况下可以装进的最大物品重量

• 接着我们来明确状态转移方程，当第 $i$ 个物品放不进背包时， $dp[i][v]=dp[i-1][v]$ ，否则在装入背包与不装入背包中择优，在剩余的重量 $dp[i-1][v-vw[i-1][0]]$ 中能装入的最大重量加上第 $i$ 个物品的重量 $vw[i-1][1]$ ，这是装入第 $i$ 个物品的前提

图片说明
• 而 $dp$ 数组的初始化为 $dp[0][…]=dp[…][0]=0$ ,即当背包中没有物品或者背包没有空间的时候，背包能装的最大重量为0
具体代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[][]dp=new int[n+1][V+1];
        //状态1是可选物品的数量，状态2是背包的容量
        for(int i=1;i<=n;i++){
            for(int v=1;v<=V;v++){
                //当前背包的容量装不下第i个物品,继承之前的背包的价值
                if(v<vw[i-1][0]){
                    dp[i][v]=dp[i-1][v];

                }
                //在背包容量允许的前提下，装入背包与不装入背包选择最大价值
                else{
                    dp[i][v]=Math.max(dp[i-1][v-vw[i-1][0]]+vw[i-1][1],dp[i-1][v]);
                }
            }
        }//循环结束，返回背包的最大重量
           return dp[n][V];
    }
}

复杂度：
•时间复杂度：因为有双重循环，时间复杂度为 $O(Vn)$

•空间复杂度： $dp$ 数组的大小， $O(Vn)$
方法二：优化后的动态规划
我们发现每次选择都只与i-1行有关，于是可以压缩二维数组为一维数组，降低空间复杂度
代码如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[]dp=new int[V+1];
        for(int i=1;i<=n;i++){
            for(int v=V;v>=1;v--){
                //背包容量大于要装入物品的容量         
                if(v>=vw[i-1][0])
                    dp[v]=Math.max(dp[v-vw[i-1][0]]+vw[i-1][1],dp[v]);
            }
        }
           return dp[V];
    }
}

复杂度：
•时间复杂度：双重循环， $O(Vn)$

•空间复杂度：与 $dp$ 数组的大小有关， $O(V)$