# Backpack IV

## unbounded knapsack problem (UKP)

## 重复选择+唯一排列+装满可能性总数

**Description**\
Given n items with size `nums[i]` which an integer array and all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

> Each item may be chosen unlimited number of times

### Example

Given candidate items`[2,3,6,7]`and target`7`,

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

## Analysis + Solution

#### 完全背包问题

借鉴Backpack III中完全背包问题的处理方法，`k * nums[i - 1] <= j`作为`nums[i - 1]` 取得个数的限制条件。

**状态**：`dp[i][j]` - 前`i`个元素，加起来能装满`j`大小的方法个数

**状态转移方程**：`dp[i][j] += dp[i - 1][j - k * nums[i - 1]; (k = 0, 1, ..., j / nums[i - 1])`

**初始化条件:** `dp[0][0] = 1`，相当于说0个元素装满0大小，这个方法有1个。并且`dp[0][i] = 0` (i > 0, i < target + 1)

注意这里是unique的组合方式，也就是说对于题目中的例子`[2,2,3]` 和 `[2,3,2]`是一样的，只能计入1个。

因此外层循环用`nums[]`，确保每次元素的选取组合不会与之前计算的重复。

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

Or Similarly

```java
    public int backPackIV(int[] nums, int target) {
        // Write your code here
        int m = target;
        int []A = nums;
        int f[][] = new int[A.length + 1][m + 1];

        f[0][0] = 1;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k * A[i-1] <= j; k++) {
                    f[i][j] += f[i-1][j-A[i-1]*k];
                }
            } // for j
        } // for i    
        return f[A.length][target];
    }
```

#### 优化空间复杂度为一维数组

为了与2D版有统一性，这里外循环用\[0, nums.length]，因此内层循环在使用时要用`nums[i - 1]`

```java
    public int backPackIV(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 = nums[i - 1]; j <= target; j++) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }

        return dp[target];
    }
```

因为这里不再需要nums.length + 1，因此也可以直接用\[0, nums.length - 1]作为外循环。

```java
public class Solution {
    public int backPackIV(int[] nums, int target) {

        int n = nums.length;
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = nums[i]; j <= target; j++) {
                f[j] += f[j - nums[i]];
            }
        }
        return f[target];
    }
}
```

## Reference

Jiuzhang Backpack Tutorial: <https://www.jiuzhang.com/tutorial/backpack/471>


---

# 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-iv.md?ask=<question>
```

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.