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

题目描述
已知一个背包最多能容纳物体的体积为V
现有n个物品第i个物品的体积为vi，第i个物品的重量为wi。求当前背包最多能装多大重量的物品

方法一：动态规划

求解思路
对于求解01背包问题，我们想到使用动态规划进行求解，可以发现，对于一个物体，我们有两种选择，放或者不放进背包。这样便将问题划分成了更小的子问题。我们使用 $dp[i][j]$ 表示当前第i个物品，背包体积为V时能够得到的最大重量和。 $vw[i][j]$ 表示题目所给的物体的体积和重量。因此根据第i-1个物品的放或者不放进背包的情况对第i个物品进行讨论，我们即可得到转移方程为： $dp[i][j] = max(dp[i][j], dp[i-1][j-vw[i-1][0]]+vw[i-1][1])$ ，最终我们得出题目要求的答案。

图片说明

解题代码

class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        vector<vector<int>> hydp(n + 1, vector<int>(V + 1));
        for(int i = 1; i <= n; ++i) 
        {
            for(int j = 1; j <= V; ++j) 
            {
                hydp[i][j] = hydp[i - 1][j]; // 不装入物品
                if(j >= vw[i - 1][0]) 
                {   //体积足够，可以装入
                    hydp[i][j] = max(hydp[i][j], hydp[i-1][j-vw[i-1][0]]+vw[i-1][1]);
                }
            }
        }
        return hydp[n][V]; // 返回结果
    }
};

复杂度分析
时间复杂度：使用了两层循环，因此时间复杂度为 $图片说明$ ,其中n为物体的个数，v为物体的体积。
空间复杂度：引入dp[n][v]数组，因此空间复杂度为 $图片说明$ ,其中n为物体的个数，v为物体的体积。

方法二：优化方法--动态优化

求解思路
对于动态规划我们对其进行优化，根据方法一的代码，我们发现每次对于i的选择都只与第i-1层相关，所以我们使用滚动数组对本题进行空间角度的优化。

图片说明

解题代码

class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        vector<int> hydp(V + 1); // 声明辅助数组
        for(int i = 1; i <= n; ++i) 
        {
            for(int j = V; j > 0; --j) // 这里使用辅助数组，在空间角度对其优化
            {
                if(j >= vw[i - 1][0]) 
                {   //体积足够，可以装入
                    hydp[j] = max(hydp[j], hydp[j - vw[i - 1][0]] + vw[i - 1][1]);
                } // 不能装入时数组大小保持原样即可
            }
        }
        return hydp[V]; // 返回结果即可
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $图片说明$ ,其中n为物体的个数，v为物体的体积。
空间复杂度：引入dp[n]数组，因此空间复杂度为 $O(N)$