Backpack 背包问题

从n个数中取，装m的包。link

Didscussion

经典背包问题，DP。 不确定取几个数，也不确定最多能装多少。

• 定义一个n+1 X m+1的数组来表示状态，f[i][j]表示从前i个数里面取几个数，可以组成和为j。

• 状态转移：$$f[i][j] = f[i-1][j - a[i-1]] or f[i-1][j]$$. f[i][j]为真（前i个和为j）当且仅当前i-1个的和可以为j或者j-a[i], 分别表示“刚好取上第i个和变为j”， “不用再取第i个了，前i-1个的和已经是是j了”

Solution

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) {
        // write your code here
        int n = A.size();
        vector<vector<bool> > f(n+1, vector<bool>(m+1, false));
        int ret = 0;
        //initialize states
        for(int i=0; i<n+1; i++) {
            f[i][0] = true;
        }
        for (int j=1; j<m+1; j++) {
            f[0][j] = false;
        }
        //function
        for(int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                if(j-A[i-1]<=m && j-A[i-1] >=0)
                     f[i][j] = f[i-1][j] || f[i-1][j-A[i-1]];//注意下标
                else
                    f[i][j] = f[i-1][j];
            }
        }
        //answer:从前
        for(int j=0; j<=m; j++) {
            if(f[n][j]) {
                ret = max(ret, j);
            }
        }
        return ret;
    }
};

两个复杂度都是$$O(nm)$$

能不能用滚动数组来降低复杂度呢？YES!

Solution 2

上面code里function部分将内层循环改成从右向左结果是一样的，这样的话每一行都是从右向左更新f[i][j], 可以设置一个滚动数组d[j]， 在更新d[j] 之前，d[j] 里保存的f[i-1][j]，更新之后，d[j] 里保存的是f[i][j]。

滚动数组+自底向上的动规

• 下面的代码是根据上面的改的，用滚动数组取代二维数组，同事自底向上更新状态。 如果是直接写"滚动数组+自底向上的动规”还真的不太好想。。。好吧。。。

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) {
        // write your code here
        int n = A.size();
        //vector<vector<bool> > f(n+1, vector<bool>(m+1, false));
        int ret = 0;
        vector<bool> state(m+1, false);
        state[0] = true;
        for(int i=0; i<n; i++) {
            for (int j=m; j>=1; j--) {
                if(j-A[i]<=m && j-A[i] >=0)
                     state[j] = state[j] || state[j-A[i]];
                else
                    state[j] = state[j];
            }
        }
        for(int j=0; j<=m; j++) {
            if(state[j]) {
                ret = max(ret, j);
            }
        }
        return ret;
    }
};