# Backpack V

## [Backpack V](https://www.lintcode.com/problem/backpack-v/description)  0-1 背包问题 <a href="#articleheader23" id="articleheader23"></a>

## 0/1 Knapsack Problem

### 单次选择+装满可能性总数 <a href="#articleheader24" id="articleheader24"></a>

#### Description

Given n items with size`nums[i]`which an integer array and all positive numbers. An integer`target`denotes 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 target`7`,

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

return`2`

### Solution & Analysis

一维DP，0-1 背包问题

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

```java
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][*]`有关，这给我了我们优化空间复杂度的契机，所有可以优化到一维。（又因为物品是取一个还是可以无限取，那么在一维状态的时候就要仔细考虑如何枚举状态的顺序）。

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

\>