Backpack Problems

初始状态：

求最大体积或最大价值时，dp[0]= 0

求组合个数时，dp[0] = 1

状态方程

考虑两种情况：不选取第i个元素放入背包，只考虑前i-1个元素，体积为j时。和放入第i个元素，体积为j - A[i]时，这时要求A[i] <= j

• 由于第i个元素状态方程只和第i-1个元素相关，因此二维数组可以优化为只和体积相关的一维数组

• 对体积从大到小遍历适用于无重复放置的情况，从小到大遍历适用于可以重复放置的情况

Complexity

O(m*n), memory O(m)