DP Knapsack Problem With Categorical Constraint

Question

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?

Answer 1

An alternative approach you could try: solve a knapsack problem for each category separately, then combine those solutions.

You'll probably find it more rewarding to work out how to do that on your own, but if you want a more detailed hint:

For each category and each total weight $w$ and each integer $t$, compute the maximum enjoyment you can have by using at most $t$ books from that category and where the total weight is at most $w$.

For instance, for each $w,t$, you'll compute the maximum enjoyment you can have by selecting at most $t$ fantasy books (and no science fiction or classic books) of weight at most $w$. Then do the same for science fiction, and the same for classic books.

Then, combine these three results. I'll let you work out how to combine them.