Skip to content

6. Backpack bounded knapsack problem (BKP)

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 I

Input: [1,2,3,3,7] and target 7, Output: A solution set is: [7],[1, 3, 3]

Question

Transform Function

dp[i][j] += dp[i][j - 1];
dp[i][j] += dp[i - 1][j - 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];
                if(j >= nums[i - 1]) dp[i][j] += dp[i - 1][j - 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 = target; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }

        return dp[target];
    }
}