# Backpack V
## [Backpack V](https://www.lintcode.com/problem/backpack-v/description) 0-1 背包问题
## 0/1 Knapsack Problem
### 单次选择+装满可能性总数
#### 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];
}
}
```
**关于(内层)循环的遍历顺序**，九章有一个问答解释的很好：
\>
首先2维的状态是一个完整的状态，能表示状态详细的信息，为什么会有变成1维，实际上是在2维的前提下，优化了空间复杂度。\
本质来说，`f[i][*]`只和`f[i - 1][*]`有关，这给我了我们优化空间复杂度的契机，所有可以优化到一维。（又因为物品是取一个还是可以无限取，那么在一维状态的时候就要仔细考虑如何枚举状态的顺序）。
接下来是关于状态顺序的枚举。就是顺序是怎么思考的。\
动态规划问题枚举的顺序只有一个**`原则`：`如果b状态的计算依赖于a状态，那么a状态必须在b状态之前被枚举和计算`**
\>
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-v.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.