Unbounded Knapsack

Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created. To create the sum, use any element of your array zero or more times.

For example, if arr=[2,3,4] and your target sum is 10, you might select [2,2,2,2,2], [2,2,2,3] or [3,3,3,1] . In this case, you can arrive at exactly the target.

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

This is a unbounded knapsack so we cannot use the classic way to solve this problem. To solve it, we can break the problem into smaller problems first.

If we put the first item into the knapsack, then the remaining capacity would be W-w1. So we can break it down to find out the maximum value max1 if we pack the same item N times in a knapsack of capacity W-w1. For the second item, we do the same thing to get max2 so that it has a remaining capacity of W-w2, and so on.

Each item has a own value now but we have to add the original value to it.

itemMax1 = max1 + v1

The maximum value is

W = max(itemMax1,itemMax2,...,itemMaxN)

where W is the maximum value packed in the knapsack of capacity.

Psuedo code

f(v[], w[], c) {
    // v: array of values
    // w: array of weights
    // c: capacity
    // n: length of the array

    // base case
    // if it is full, the total value of a 0 capacity knapsack is 0
    if(c==0) return 0;

    int[] m;

    // break it down to smaller problem
    // ----------------------------------------
    for(int i=0;i<n;i++){
        // if we can put item 1
        if(w[i]<c) m[i]=f(v,w,c-w[i]);
        // not enough space
        else m[i]=0; 
    }

    // add back the original value
    // ----------------------------------------
    for(int i=0;i<n;i++){
        // if we can put item 1
        if(w[i]<c) mm[i]=m[i] + v[i];
        // not enough space
        else mm[i]=0; 
    }

    // find the maximum value
    // ----------------------------------------
    int ans=mm[0];
    for(int i=1;i<n;i++){
        if(mm[i]>ans) ans=mm[i];
    }

    return ans;
}

However, we can use bottom-up dynamic programming solution for this problem to improve the above solution.

As we may see that we only have one parameter c for the recursive method where c ranges from W to 0 and v[] and w[] remain unchanged. Therefore, we can store the results computed by the recursive function in a 1d array.

int dp[W+1];

We can set our base case to 0.

dp[0] = 0;

We can turn

f(v,w,c-w[i]);

to

dp[c-w[i]]

and also from

int ans=mm[0];
for(int i=1;i<n;i++){
    if(mm[i]>ans) ans=mm[i];
}

return ans;

to

dp[c]=mm[0];
for(int i=1;i<n;i++){
    if(mm[i]>dp[c]) dp[c]=mm[i];
}

and the result would be

return dp[c];

So we have the following structure

dp[0] = 0

for C=0 ... W:
    for i=0 .. N:
        if w[i]<=C: 
            dp[i] = max ( dp[i], ( dp[C-w[i]] + v[i] ) )
        else 
            dp[i] = 0