The typical unbounded (allowed to choose unlimited amount of each item) knapsack

Question

The typical unbounded (allowed to choose unlimited amount of each item) knapsack problem can be solved using the following algorithm:

// the following algorithm returns the maximum value with knapsack of C capacity aka unbounded knapsack (I can choose unlimited amount of each item)

// N = number of types of items, W[] = weight of each type of item, V[] = value of each type of item, C = the capacity limit of the knapsack, L[] = quantity of each type of item

public static int solve(int N, int[] W, int[] V, int[] L, int C) {
  
// results[i] is going to store maximum value with knapsack capacity i
int results[] = new int[C+1];
// initialise array to 0
Arrays.fill(results, 0);

// Fill dp[] using bottom up DP approach
for (int i=0; i<=C; i++)
for (int j=0; j<N; j++)
if (W[j] <= i)
results[i] = Math.max(results[i], results[i-W[j]]+V[j]);

return results[C];
}

Suppose the array L[] stores the quantity of each item that I can choose from. How do I tweak the unbounded knapsack algorithm (and make use the array L[]) to return the optimal knapsack with the additional constraint on the quantity of each item I can choose?

Explanation / Answer

Its an unbounded knapsack problem as we can use 1 or more instances of any resource. A simple 1D array, say dp[W+1] can be used such that dp[i] stores the maximum value which can achieved using all items and i capacity of knapsack. Note that we use 1D array here which is different from classical knapsack where we used 2D array. Here number of items never changes. We always have all items available.

We can recursively compute dp[] using below formula

Below is C++ implementation of above idea.

// C++ program to find maximum achievable value

// with a knapsack of weight W and multiple

// instances allowed.

#include<bits/stdc++.h>

using namespace std;

// Returns the maximum value with knapsack of

// W capacity

int unboundedKnapsack(int W, int n, int val[], int wt[])

{

    // dp[i] is going to store maximum value

    // with knapsack capacity i.

    int dp[W+1];

    memset(dp, 0, sizeof dp);

    int ans = 0;

    // Fill dp[] using above recursive formula

    for (int i=0; i<=W; i++)

      for (int j=0; j<n; j++)

         if (wt[j] <= i)

            dp[i] = max(dp[i], dp[i-wt[j]]+val[j]);

    return dp[W];

}

// Driver program

int main()

{

    int W = 100;

    int val[] = {10, 30, 20};

    int wt[] = {5, 10, 15};

    int n = sizeof(val)/sizeof(val[0]);

    cout << unboundedKnapsack(W, n, val, wt);

    return 0;

}

// C++ program to find maximum achievable value

// with a knapsack of weight W and multiple

// instances allowed.

#include<bits/stdc++.h>

using namespace std;

// Returns the maximum value with knapsack of

// W capacity

int unboundedKnapsack(int W, int n, int val[], int wt[])

{

    // dp[i] is going to store maximum value

    // with knapsack capacity i.

    int dp[W+1];

    memset(dp, 0, sizeof dp);

    int ans = 0;

    // Fill dp[] using above recursive formula

    for (int i=0; i<=W; i++)

      for (int j=0; j<n; j++)

         if (wt[j] <= i)

            dp[i] = max(dp[i], dp[i-wt[j]]+val[j]);

    return dp[W];

}

// Driver program

int main()

{

    int W = 100;

    int val[] = {10, 30, 20};

    int wt[] = {5, 10, 15};

    int n = sizeof(val)/sizeof(val[0]);

    cout << unboundedKnapsack(W, n, val, wt);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.