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

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!