背包问题总结 (Backpack Problem)

本文主要总结Lintcode的Backpack Problem I - VI. Backpack的解题思路是建立二维表。fill matrix。用到dp[i][j] 的二维DP数组。

Backpack I:
www.lintcode.com/problem/backpack

设dp[i][j] 为前Item I，取size <= j 的最大值，则有两种可能。1. 不拿item i，dp[i][j] = dp[i-1][j]; 2. 拿item i，dp[i][j] = dp[i-1][j-A[i]] + A[i]。所以通项公式为：
dp[i][j] = max(dp[i-1][j] + dp[i-1][j-A[i]] + A[i])

int backPack(int m, vector<int> A) {
        // write your code here
        if(A.empty()) return 0;
        int n = A.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(j < A[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1]);
                }
            }
        }
        return dp[n][m];
    }

Backpack II:
http://www.lintcode.com/en/problem/backpack-ii/#

题中加入了value元素，基本没有变化。dp[i][j] 为前i个，组成size <= j的最大value值，所以通项改为
dp[i][j] = max(dp[i-1][j] + dp[i-1][j-A[i]] + V[i])

int backPackII(int m, vector<int> A, vector<int> V) {
        // write your code here
        if(m <= 0 || A.empty() || A.size() != V.size()) return 0;
        int n = A.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(j < A[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }
        return dp[n][m];
    }

Backpack III:
http://www.lintcode.com/en/problem/backpack-iii/#

Backpack III 是无限背包，表示每一个item可以取无数次。
所以通项定义稍有变化。dp[i][j] 为当前到第i个item，拿到size <= j 的最大价值。所以有最后不取第i个item，dp[i][j] = dp[i-1][j], 取第i个item，由于之前也可以取item i，dp[i][j] = dp[i][j-A[i]] + A[i]

通项公式为：
dp[i][j] = max(dp[i-1][j] + dp[i][j-A[i]] + A[i])

int backPackIII(vector<int>& A, vector<int>& V, int m) {
 // Write your code here
    if(m <= 0 || A.empty() || A.size() != V.size()) return 0;
    int n = A.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j < A[i-1]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-A[i-1]] + V[i-1]);
            }
        }
    }
    return dp[n][m];
 }

Backpack IV:
http://www.lintcode.com/en/problem/backpack-iv/#

求方案个数，求方案个数就是把取max，变成求和。由于还是无限背包，即每个item可以用无数次，所以还是看同一行。通项公式如下：
dp[i][j] 为取到前i个数，组成size <= j 的总方案个数。
dp[i][j] = dp[i-1][j] + dp[i][j-A[i]];

初始化时，要把起始整个column都设为1.

int backPackIV(vector<int>& nums, int target) {
        // Write your code here
        if(nums.empty()) return 0;
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
        for(int i=1; i<=n; i++){
            dp[i][0] = 1;
            for(int j=1; j<=target; j++){
                if(j < nums[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }

Backpack V:
http://www.lintcode.com/en/problem/backpack-v/

这道题就是与IV相比，去掉了无限背包的条件，每个item用一次。
dp[i][j] 为前i个item，去size <= j 的方案个数。通项公式为
dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]]; 与I and II 类似。

int backPackV(vector<int>& nums, int target) {
        // Write your code here
        if(nums.empty() || target <= 0) return 0;
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
        dp[0][0] = 1;
        for(int i=1; i<=n; i++){
            dp[i][0] = 1;
            for(int j=1; j<=target; j++){
                if(j<nums[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }

或者用下面的方法

 int findSum(vector<int>& nums, int target){
        int len = nums.size();
        int *dp = new int[target+1];
        fill_n(dp, target+1, 0);
        dp[0] = 1;
        for(int i=0; i<nums.size(); i++){
            for(int j=target; j>=nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }

Backpack VI:
http://www.lintcode.com/en/problem/backpack-vi/

这道题就是combination sum，代码如下:

int backPackVI(vector<int>& nums, int target) {
 // Write your code here
    if(target <= 0 || nums.empty()) return 0;
    int n = nums.size();
    vector<int> dp(target+1, 0);
    dp[0] = 1;
    for(int i=1; i<=target; i++){
        for(int j=0; j<n; j++){
            if(i >= nums[j]) dp[i] += dp[i-nums[j]];
        }
    }
    return dp[target];
 }