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 target7,

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[]，确保每次元素的选取组合不会与之前计算的重复。

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

    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]

    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]作为外循环。

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