题解 | #01背包#

递归+记忆化搜索，时空复杂度高于动态规划，但是却很好理解。

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
        //记忆化搜索：第一维代表有n个物品。第二维代表最大重量，当最大重量是0的时候，肯定初始值也是0嘛
        vector<vector<int> > memo(n,vector<int>(V + 1,0));
        test(V,n - 1,vw,memo);
        return memo[n-1][V];
    }
    
    int test(int V,int n,vector<vector<int> >& vw,vector<vector<int> >& memo){
        //出口:当没有物品或者体积为0时
        if(V <= 0 || n == -1) return 0;
        //记忆化搜索
        if(memo[n][V] != 0) return memo[n][V];
        
        //状态转移方程
        if(V - vw[n][0] < 0){
            memo[n][V] = test(V,n - 1,vw,memo);
            return memo[n][V];
        }
        else{
            memo[n][V] = max(test(V,n - 1,vw,memo),test(V - vw[n][0],n - 1,vw,memo) + vw[n][1]);
            return memo[n][V];
        }
    }
};