【LintCode刷题】125. 背包问题 II

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

样例
样例 1:

输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
样例 2:

输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
输出: 10
解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10
挑战
O(nm) 空间复杂度可以通过, 不过你可以尝试 O(m) 空间复杂度吗?

注意事项
A[i], V[i], n, m 均为整数
你不能将物品进行切分
你所挑选的要装入背包的物品的总大小不能超过 m
每个物品只能取一次

思路：和背包问题类似，对于N个物品，能否拼出重量w,对于重量w,其对应的最大价值是多少。

步骤一：确定状态

例子：

步骤二：得出子问题

步骤三：确定转移方程。

步骤四：确定初始条件和边界条件。

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        int n = A.size();
        int l = V.size();
        if(n == 0 || l == 0)
            return 0; 
            
        vector<vector<int>>f(n + 1,vector<int>(m + 1));
        f[0][0] = 0;
        
        for(int i = 1;i<=m;++i)
        {
            f[0][i] = -1;//0个物品是拼不出价值为i的
        }
        
        for(int i = 1;i <=n; ++i)
        {
            for(int w = 0;w <= m;++w)
            {
                f[i][w] = f[i - 1][w];//假设可以用前i - 1个物品拼出重量w(其实还有待考察)（可以利用后面的更新）
                if(w >= A[i - 1] && f[i - 1][w - A[i - 1]] != -1)
                {
                    f[i][w] = max(f[i][w],f[i - 1][w - A[i - 1]] + V[i -1]);//图中的转移方程
                }
            }
        }
        
        int res = 0;
        for(int w = 0;w <= m;++w)
        {
            if(f[n][w] != -1)
            {
                res = max(res,f[n][w]);
            }
        }
        return res;
    }
};