2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ ah sorry, W isn't a double. That was a mistake. It's always an integer. You have a list of n items, each with an enjoyment value e(i) and a weight w(i) and genre g(i) where i is the item. Maximize the sum of e(i) and sum of w(i) <= W with at least O items from each category. Essentially it's just the knapsack problem with values and weights, except the value is the enjoyment and each item gets an extra "category" variable (there are 3 categories). $\endgroup$ – Jeremiah Cummings Feb 16 '17 at 21:01
  • $\begingroup$ OK. Cool. Can you edit the question to incorporate that information, and to fix the code so it doesn't imply W is a double? We want questions to read well for someone who encounters them the first time, and to be self-contained, so readers don't have to read the comments. (Comments are transitory notes that can disappear and exist mainly to help you improve the question.) Thank you! $\endgroup$ – D.W. Feb 16 '17 at 21:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought of this, but I totally missed the combining it aspect because I didn't try varying the parameter $w$ to get all possible weight combinations. Thanks! This really helps. $\endgroup$ – Jeremiah Cummings Feb 16 '17 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.