背包的系列问题，从01背包开始 动态规划与分治法类似，都是把大问题拆分为小问题，通过寻找大问题与小问题之间的递推关系，解决一个个小问题，最终达到解决原问题的效果。不同的是，分治法在子问题和子子问题上被重复计算了多次，而动态规划具有记忆性，通过填表把已经解决的子问题的答案记录下来，在新问题里需要用到的数据可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划问题的核心就在于“填表”！表填写完毕，最优解也就找到了

背包问题的解决过程： 如果使用暴力穷举，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是O(2^N)，这是不可接受的。而使用动态规划可以将复杂度降至O(NW)。我们的目标是书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态dp: dp[i][j]表示将前i件物品装进体积为j的背包可以获得的最大重量, 0<=i<=N, 0<=j<=V

那么我们将dp[i][0]和do[j][0]都初始化为0 面对i>0,有两种情况：

  1. 不装入第i件物品，即dp[i−1][j]；
  2. 装入第i件物品（前提是能装下），即dp[i−1][j−w[i]] + v[i]。

即状态转移方程为： dp[i][j] = max(dp[i−1][j], dp[i−1][j−vw[i][0]]+vw[i][1]) // j >= vw[i][0]

因此，未优化的程序如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<vector<int>> copy(n+1,vector<int>(3, 0));
        for(int i=0;i<n;i++)
            for(int j=0;j<2;j++)
                copy[i+1][j+1]=vw[i][j];
        int dp[n+1][V+1];
        //dp[i][j]表示前i个物品 在体积限制为V的情况下，可以获得的最大重量
        for(int i=0;i<=V;i++)
            dp[0][i]=0;
        for(int i=0;i<=n;i++)
            dp[i][0]=0;
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=V;j++)
            {
                if(j>=copy[i][1])
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-copy[i][1]]+copy[i][2]);
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n][V];
    }
};

具体索引到加入的是第几个物品，可以参考这篇博客： 【动态规划】01背包问题（通俗易懂，超基础讲解）

优化问题：参考滚动数组 下面这篇博客： 动态规划——背包问题 学习后的可运行程序：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    #define N 1001
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<vector<int>> copy(n+1,vector<int>(3, 0));
        for(int i=0;i<n;i++)
            for(int j=0;j<2;j++)
                copy[i+1][j+1]=vw[i][j];
        int f[N]={0};
        
        for(int i=1;i<=n;i++)
        {
            for(int j=V;j>=copy[i][1];j--)
            {
                f[j]=max(f[j],f[j-copy[i][1]]+copy[i][2]);
            }
        }
        return f[V];
    }
};