LintCode 562: Backpack IV (完全背包问题变种，DP经典)

这题就是完全背包的变种。
dp[x]表示能装满size 为x的背包的最多方法总数。
注意：

1. dp[j] += dp[j - nums[i]];
   旧的dp[j]: 上次的# of ways to fill size=j knapsack with item i
   旧的dp[j-nums[i]]: 上次的# of ways to fill size=j-nums[i] knapsack without item i
   所以两者加起来就是这次的# of ways to fill size=j knapsack with item i。
2. dp[0] = 1，要不然dp[]会全0。

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    int backPackIV(vector<int> &nums, int target) {
        int n = nums.size();
        vector<int> dp(target + 1 , 0); //dp[x] shows the max ways that can fill size x knapsack
        
        dp[0] = 1;        
        for (int i = 0; i < n; ++i) {
            
            for (int j = nums[i]; j <= target; ++j) {

                dp[j] += dp[j - nums[i]];  //old dp[j] is the # of ways to fill j that do have item i,
                                           //dp[j - nums[i]] is the # of ways to fill j- nums[i] that do not have item i

            }
        }
        
        return dp[target];
    }
};

注意：

1. 下面的方法不对：

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    int backPackIV(vector<int> &nums, int target) {
        int n = nums.size();
        int count = 0;
        vector<int> dp(target + 1 , 0); //dp[x] shows the max volumes that the size x knapsack can hold. 
        
        for (int i = 0; i < n; ++i) {
            for (int j = nums[i]; j <= target; ++j) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
   //             cout<<"i = "<<i<<" j = "<<j<<" "<<dp[j]<<endl;
                if (dp[j] == target) count++;
            }
        }
        
        return count;
    }
};

该方法用dp[x]表示size=x的knapsack的最多可以装满的大小。
在j循环内判断dp[x]是否等于target，若是，则count++。最后返回count。
该方法的问题在什么地方呢?
我们针对输入
[2,2,3]
7
其debug信息如下：
i = 0 j = 2 2
i = 0 j = 3 2
i = 0 j = 4 4
i = 0 j = 5 4
i = 0 j = 6 6
i = 0 j = 7 6
i = 1 j = 2 2
i = 1 j = 3 2
i = 1 j = 4 4
i = 1 j = 5 4
i = 1 j = 6 6
i = 1 j = 7 6
i = 2 j = 3 3
i = 2 j = 4 4
i = 2 j = 5 5
i = 2 j = 6 6
i = 2 j = 7 7
Output
1
Expected
3

我们可以看出，在i,j两层循环种，dp只有1次达到了7。这是因为dp[7]实际上几种最优解都包括了，但只算了一种。

2. 这题也不能用LintCode 564: Combination SumIV的方法，即将i,j循环简单的倒过来。因为LintCode 564是取硬币，[1, 1, 2], [1, 2, 1] and [2, 1, 1] 算了3组，而这里只能算1组。