//我先写了递归的做法，进而从暴力递归到动态规划，水到渠成
/*
class Solution {
  public:
    //现在进行到了index位置的物品进行选择，背包还剩remain个空间
    //返回的是得到的背包最大的重量
    int f(int remain, int n, vector<vector<int> >& vw, int index) {
        if (index == n) return 0;
        if (remain == 0) return 0;
        //选了index物品
        int p1 = 0;
        if (remain - vw[index][0] >= 0) {
            p1 = vw[index][1] + f(remain - vw[index][0], n, vw, index + 1);
        }
        //没选index物品
        int p2 = f(remain, n, vw, index + 1);
        int ans = p1 > p2 ? p1 : p2;
        return ans;
    }
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        return f(V, n, vw, 0);
    }
};//递归做法
*/

class Solution {
  public:
    //现在进行到了index位置的物品进行选择，背包还剩remain个空间
    //返回的是得到的背包最大的重量
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        vector<int> start(n+1,0);
        vector<vector<int>> dp(V+1,start);
        for(int index=n-1;index>=0;index--){
            for(int remain=0;remain<=V;remain++){
                int p1=0;
                if (remain - vw[index][0] >= 0) {
                    p1 = vw[index][1] + dp[remain - vw[index][0]][index + 1];
                }
                int p2=dp[remain][index + 1];
                dp[remain][index]=p1>p2?p1:p2;
            }
        }

        return dp[V][0];
    }
};//dp做法