[LintCode] BackPack I

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

注意事项

你不可以将物品进行切割。

样例

如果有4个物品[2, 3, 5, 7]

如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。

如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。

函数需要返回最多能装满的空间大小。

挑战

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

经典01背包问题。利用二维数组的状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i])

空间复杂度O(N * M)

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
        if (A.empty() || m == 0)
            return 0;
        vector<vector<int>> dp(A.size(), vector<int>(m + 1, 0));
        for (int j = 0; j != m + 1; j++) {
            if (j >= A[0])
                dp[0][j] = A[0];
        }
        for (int i = 1; i != A.size(); i++) {
            for (int j = 1; j != m + 1; j++) {
                if (j >= A[i])
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[A.size() - 1][m];
    }
};

MLE

对二维数组进行优化，由于背包的状态只与相邻两行的数组有关，所以利用行数的奇偶来进行优化。维护一个只有2行的二维数组。状态转移方程：dp[i % 2][j] = max(dp[abs(i % 2 - 1)][j], dp[abs(i % 2 - 1)][j - A[i]] + A[i])

空间复杂度O(2 * M)

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
        if (A.empty() || m == 0)
            return 0;
        vector<vector<int>> dp(2, vector<int>(m + 1, 0));
        for (int j = 0; j != m + 1; j++) {
            if (j >= A[0])
                dp[0][j] = A[0];
        }
        for (int i = 1; i != A.size(); i++) {
            for (int j = 1; j != m + 1; j++) {
                if (j >= A[i])
                    dp[i % 2][j] = max(dp[abs(i % 2 - 1)][j], dp[abs(i % 2 - 1)][j - A[i]] + A[i]);
                else
                    dp[i % 2][j] = dp[abs(i % 2 - 1)][j];
            }
        }
        return dp[(A.size() - 1) % 2][m];
    }
};

对空间复杂度进行优化，利用一个一维数组表示原来二维数组的状态。需要注意的是只有对内层for循环逆序遍历才可以表示状态的递推关系

空间复杂度O(M)

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
        if (A.empty() || m == 0)
            return 0;
        vector<int> dp(m + 1, 0);
        for (int i = 0; i != A.size(); i++) {
            for (int j = m; j != 0; j--) {
                if (j >= A[i])
                    dp[j] = max(dp[j], dp[j - A[i]] + A[i]);
                else
                    dp[j] = dp[j];
            }
        }
        return dp[m];
    }
};

参考资料：

背包九讲之01背包问题

背包问题之01背包、完全背包、多重背包详解