The typical unbounded (allowed to choose unlimited amount of each item) knapsack
ID: 3600701 • Letter: T
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 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 a new 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?
Thanks in advance!
Explanation / Answer
public static int solve(int N, int[] W, int[] V, int C) {
int i, j;
// results[i] is going to store maximum value with knapsack capacity i
int results[][] = new int[C + 1][W + 1];
int L[] = new int[C + 1];
// initialise array to 0
for(i = 0; i <= C; i++) {
for (j = 0; i <= N; j++) {
results[i][j] = 0;
}
}
// Fill dp[] using bottom up DP approach
for(i = 1; i <= C; i++) {
for(j = 1; j <= N; j++) {
if(W[i] <= j) {
L[i] = Math.Min(V[i], j / V[i]);
results[i][j] = getMax(results[i-1][j], V[i] + results[i-1][j - W[i]]);
} else {
results[i][j] = results[i - 1][j];
}
}
}
return results[N][C];
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.