【LintCode刷题】92. 背包问题

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

样例
样例 1:
输入: [3,4,8,5], backpack size=10
输出: 9

样例 2:
输入: [2,3,5,7], backpack size=12
输出: 12

挑战
O(n x m) 的时间复杂度 and O(m) 空间复杂度
如果不知道如何优化空间O(n x m) 的空间复杂度也可以通过.

思路：本题是大名鼎鼎的背包问题。动态规划来解决。

给定了背包的重量m,如果可能的话，理论上能够装的最大的重量应该是m（取决于我们物品的重量）。每个装物品的方案的总重量都是0到m,对于每个总重量，我们需要知道能不能有方案做到可以装到这个重量就可以了。

我们首先来确定动态规划的状态：

1. 需要知道i个物品是否能够拼出重量w;w = 0,1,2....m
2. 最后一步：当前物品（重量Ai-1 (i-1)为索引）是否进入背包
   1). 如果前i-1个物品能拼出w，那么前i个物品当然也可以拼出w;
   2). 如果前i-1个物品能拼出w - Ai-1，那么加上当前的物品Ai-1，则也是可以拼出w的。

我们再来确定子问题：

1. 要求前i个物品能不能拼出重量0,1,...,m
2. 需要知道前i-1个物品能不能拼出 0,1,...,m

我们定义状态：
设f[i][w]为“能否用前i个物品拼出重量w” （注意一下容易犯错的点）

转移方程：

代码实现：

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> &A) {
        int n = A.size();
        if(n == 0)
            return 0;//0个物品拼出重量0
        
        vector<vector<bool>> f(n + 1,vector<bool>(m + 1,false)); 
        
        f[0][0] = true;//前0个物品可以拼出重量0
        
        for(int i = 1;i <= n;++i)
        {
            for(int j = 0;j <= m;++j)
            {
                f[i][j] = f[i - 1][j];//表示前i-1个物品能否拼出重量j
                if(j >= A[i - 1])
                {
                    f[i][j] = f[i][j] || f[i - 1][j - A[i - 1]];
                }
            }
        }
        
        int res = 0;
        for(int i = m;i>=0;--i)//从后往前找最大能装入的重量
        {
            if(f[n][i] == true)
            {
                res = i;
                break;
            }
        }
        return res;
    }
};