> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-iv.md).

# 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>