Skip to content

5. Backpack bounded knapsack problem (BKP)

Description

Given an integer array nums[] which contains n unique positive numbers, num[i] indicate the size of ith item. An integer target denotes the size of backpack. Find the number of ways to fill the backpack. Each item may be chosen unlimited number of times

Example I

Input: nums = [2,3,6,7] and target = 7 Output: 2 Explanation: Solution sets are: [7], [2, 2, 3]

Example II

Input: nums = [2,3,4,5] and target = 7 Output: 3 Explanation: Solution sets are: [2, 5], [3, 4], [2, 2, 3]

Question

Transform Function

dp[i][j] += dp[i][j - 1];
dp[i][j] += dp[i - 1][j - k * nums[i - 1]];

Template

class Solution {
    public int backpack(int[] nums, int target) {
        int n = nums.length;
        int[][] dp = new int[n + 1][target + 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];
    }
}

Optimize I

class Solution {
    public int backpack(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];
    }
}