Skip to content

7. Backpack bounded knapsack problem (BKP)

Description

Give some coins of different value and their quantity. Find how many values which are in range 1 ~ n can these coins be combined

Example I

Input: n = 5 value = [1,4] amount = [2,1] Output: 4
Explanation: They can combine 4 numbers which are 1,2,4,5.

Example II

Input: n = 10 value = [1,2,4] amount = [2,1,1] Output: 8 Explanation: They can combine 8 numbers which are 1 ~ 8.

Question

Transform Function

dp[i][j] = dp[i - 1][j];
dp[i][j] |= dp[i - 1][j - k * value[i - 1]];

Template

class Solution {
    public int backpack(int n, int[] value, int[] amount) {
        int m = value.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                for(int k = 1; k <= amount[i - 1] && k * value[i - 1] <= j; k++) {
                    dp[i][j] |= dp[i - 1][j - k * value[i - 1]];
                }
            }
        }

        int sum = 0;
        for(int i = 1; i <= n; i++) sum += dp[m][i] == true ? 1 : 0;

        return sum;
    }
}

Optimize Analysis

dp[i][j] : how many item i will be remained, when using items before i to get j;

initialization: 
long[][] dp = new long[m + 1][n + 1];
Arrays.fill(dp[0],-1);
dp[0][0] = 0;

transform function:
            amount[i - 1]                   (dp[i - 1][j] >= 0)
dp[i][j] =  -1                              (j < value[i - 1] || dp[i][j - value[i - 1]] <= 0)
            dp[i + 1][j - value[i - 1] - 1  (other)

Optimize I (Memory Limit Exceeded)

class Solution {
    public int backpack(int n, int[] value, int[] amount) {
        int m = value.length;
        long[][] dp = new long[m + 1][n + 1];
        Arrays.fill(dp[0],-1);
        dp[0][0] = 0;

        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(dp[i - 1][j] >= 0) {
                    dp[i][j] = amount[i - 1];
                }else if(j < value[i - 1] || dp[i][j - value[i - 1]] <= 0) {
                    dp[i][j] = -1;
                }else{
                    dp[i][j] = dp[i][j - value[i - 1]] - 1;
                }
            }
        }

        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            if (dp[m][i] >= 0) sum++;
        }
        return sum;
    }
}

Optimize II

class Solution {
    public int backpack(int n, int[] value, int[] amount) {
        int m = value.length;
        long[] dp = new long[n + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(dp[j] >= 0) {
                    dp[j] = amount[i - 1];
                }else if(j < value[i - 1] || dp[j - value[i - 1]] <= 0) {
                    dp[j] = -1;
                }else{
                    dp[j] = dp[j - value[i - 1]] - 1;
                }
            }
        }
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            if (dp[i] >= 0) sum++;
        }
        return sum;
    }
}

Optimize III

class Solution {
    public int backpack(int n, int[] value, int[] amount) {
        int m = value.length;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        int res = 0;
        for(int i = 1; i <= m; i++) {
            int[] cnt = new int[n + 1];
            for(int j = value[i - 1]; j <= n; j++) {
                if(!dp[j] && dp[j - value[i - 1]] && cnt[j - value[i - 1]] < amount[i - 1]) {
                    res++;
                    dp[j] = true;
                    cnt[j] = cnt[j - value[i - 1]] + 1;
                }
            }
        }

        return res;
    }
}