I have a problem in my Algorithms Class which i am trying to solve for the past two days but I can't. I want to fully fill a container with the MINIMUM number of given boxes with dynamic programming. My container has a certain size and I have different box sizes AND quantities of them (so i have 24 boxes of size 20, 15 boxes of size 48 etc). I think that i gotta somehow modify the knapsack problem? But the knapsack is not necessarily fully filled whilst in my problem i have to fill the container completely. Also I gotta somehow connect the hypothetical value of the knapsack with the sizes of the boxes. Any hints?

  • $\begingroup$ Rather than thinking about how to modify the knapsack problem, I suggest thinking about how to define subproblems. As a side issue, with the knapsack problem, if values are proportional to weights, then the knapsack will be fully filled, if it's possible to do so. $\endgroup$ – j_random_hacker May 31 '17 at 8:28
  • $\begingroup$ In order to define the subproblems you mean make the recursive equation? I sure can't do that. Also, there's no any special relation between # of boxes - quantity of them. $\endgroup$ – Georgio3 May 31 '17 at 8:44
  • $\begingroup$ Yes, I mean that. Usually a good first way to try is to define a series of $n$ subproblems, where the $i$-th subproblem consists of the first (or last) $i$ items. Have a look at the recursive equation that is being solved by the "usual" pseudopolynomial-time algorithm (I believe this is the one on the Wikipedia page) for the knapsack problem, and maybe the equations for other DP-solvable problems, to get some inspiration. I have to work now, but I will come back to this tonight. $\endgroup$ – j_random_hacker May 31 '17 at 8:54
  • $\begingroup$ We get asked a lot about how to solve dynamic programming exercises, so we've written some guidance about how to approach that systematically: cs.stackexchange.com/tags/dynamic-programming/info. I encourage you to read that, try applying those methods, and if you're still stuck, edit the question to show how far along that chain you've gotten, what progress you've made, and where you got stuck. $\endgroup$ – D.W. May 31 '17 at 15:35

Stripping away the "story", your problem is that you have a list of numbers $v_1, \dots, v_k$ along with a target $t$ and you're looking for a set $I\subseteq \{1, \dots, k\}$ such that $\sum_{i\in I}v_i = t$. (That is, you're looking for a collection of the numbers that add up to $t$ and you can't use any number more times than it appears in the initial list.) This is known as the subset sum problem.

You can solve it with classical dynamic programming. The intuition for all such dynamic programming problems is the following.

  • Step through the values $v_i$, $1\leq i\leq k$ one at a time.
  • Any sum that can be made from $v_1, \dots, v_i$ either contains $v_i$ or it doesn't.
    • If it contains $v_i$, then its value is $v_i$ plus some sum you can make from $v_1, \dots, v_{i-1}$;
    • if it doesn't, it's just a sum from $v_1, \dots, v_{i-1}$.

Naively, you'd do this by recursion but that involves lots of recalculation so it's very inefficient. Instead, you build up a table that tells you, for each $i$ and each possible sum $s\leq t$, whether you can make sum $s$ from $v_1, \dots, v_i$.


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.