Backpack V

Backpack V 0-1 背包问题

0/1 Knapsack Problem

单次选择+装满可能性总数

Description

Given n items with sizenums[i]which an integer array and all positive numbers. An integertargetdenotes the size of a backpack. Find the number of possible fill the backpack.

Each item may only be used once

Example

Given candidate items[1,2,3,3,7]and target7,

A solution set is: 
[7]
[1, 3, 3]

return2

Solution & Analysis

一维DP，0-1 背包问题

注意这里因为是 0 -1背包问题，与Backpack IV相比，就要将内层循环遍历方向逆序，因为需要确保每个元素最多只能用一次。

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }

        return dp[target];
    }
}

关于(内层)循环的遍历顺序，九章有一个问答解释的很好：

https://www.jiuzhang.com/qa/2863/

>

首先2维的状态是一个完整的状态，能表示状态详细的信息，为什么会有变成1维，实际上是在2维的前提下，优化了空间复杂度。 本质来说，f[i][*]只和f[i - 1][*]有关，这给我了我们优化空间复杂度的契机，所有可以优化到一维。（又因为物品是取一个还是可以无限取，那么在一维状态的时候就要仔细考虑如何枚举状态的顺序）。

接下来是关于状态顺序的枚举。就是顺序是怎么思考的。 动态规划问题枚举的顺序只有一个原则：如果b状态的计算依赖于a状态，那么a状态必须在b状态之前被枚举和计算

>