so I'm working on a variation of the knapsack problem which includes a constraint on the number of each item from each category in addition to a weight. For instance, we have a number of books each given a genre (1 of 3 genres), and our goal is to maximize the total weight as well as include at least G books from each genre.
The recursion is found below, but when trying to convert this to a DP solution I'm having some issue. Note that the problem specifically deals with books, their categories, and maximizing an enjoyment factor up to some k. It's identical to the knapsack problem beyond the fact that the items are categorized and we need at least N items from each category.
private double S2(int W, int k, List<Book> books, int F, int SC, int C) {
if(W == 0 || k == -1) {
if(F <= 0 && SC <= 0 && C <= 0) {
return 0.0;
} else {
return Double.NEGATIVE_INFINITY;
}
}
Book b = books.get(k);
int w = b.getWeight();
if(W-w >= 0) {
int newF = F;
int newSC = SC;
int newC = C;
if(b.getGenre() == Book.Genre.FANTASY) {
newF = F-1;
}
if(b.getGenre() == Book.Genre.SCIENCE_FICTION) {
newSC = SC-1;
}
if(b.getGenre() == Book.Genre.CLASSICS) {
newC = C-1;
}
return Math.max(b.enjoyment+S2(W-w, k-1, books, newF, newSC, newC), S2(W, k-1, books, F, SC, C));
} else {
return S2(W, k-1, books, F, SC, C);
}
}
My DP solution involves a 5 dimensional array for W, k, F, SC, C and I'm just traversing it in 5 dimensions and filling in each value based on the recursion but it's way too slow--in fact, slower than the recursion for small n (even though it should run in polynomial time as opposed to exponential time). Is there some quicker way to traverse the subproblems in the DP solution, in some specific order?
I'm basically doing "tabular memoization" in 3 extra dimensions for the original Knapsack problem with only 1 constraint. Is my recursion wrong? Or is this to be expected?