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

// 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

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];
}

How do I go about tweaking this algorithm when there is an array L[] that stores the quantity of each item? i.e. for each item, there is a limited quantity of it that you can put in the knapsack. In other words, it's a limited bound knapsack problem, where there is a bound in each of the item you are allowed to choose.

I know of the unbounded knapsack algorithm (where you can choose an unlimited amount of each item) and the 1/0 bounded knapsack algorithm (where you can only choose each item once). But what about the limited bound knapsack problem where you can choose more than 1 of each item but there is a limit of each item you can choose?

I know I'll have to update the values in the L[] array somewhere (so that I'm keeping track of the quantity of each item and do not take something that I've ran out of) but I'm not sure of how to go about updating it.

Thanks in advance!

Explanation / Answer

// 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.