2
$\begingroup$

I'm working with a problem that is similar to the box stacking problem that can be solved with a dynamic programming algorithm. I read posts here on SO about it but I have a difficult time understanding the DP approach, and would like some explanation as to how it works. Here's the problem at hand:

Given $X$ objects, each with its own weight $w$ and strength $s$, how many can you stack on top of each other? An object can carry its own weight and the sum of all weights on top of it as long as it does not exceed its strength.

I understand that it has an optimal substructure, but its the overlapping subproblem part that confuses me. I'm trying to create a recursion tree to see where it would calculate the same thing several times, but I can't figure out if the function would take one or two parameters for example. Also I need to figure out what the recurrence relation is, which I find difficult.

$\endgroup$

closed as off-topic by D.W. Jan 3 '17 at 5:25

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Delete(remove) any object who's weight is less than strength. Sort the remaining objects in descending order of strength. From strongest to weakest. $\endgroup$ – Tobi Alafin Dec 30 '16 at 13:58
  • $\begingroup$ Can you indicate the source of this problem (providing proper attribution for your sources)? Can you link to the SO posts you're referring to and tell us what your specific confusion is? Also, what have you tried? You might want to refer to our reference material on dynamic programming, and then show us what progress you've made. What choice of subproblems have you tried? $\endgroup$ – D.W. Jan 3 '17 at 5:19
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/68049/755, stackoverflow.com/q/41361652/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Jan 3 '17 at 5:25
  • $\begingroup$ I'm voting to close this question, even though it is on-topic here, because it was simultaneously cross-posted on Stack Overflow. $\endgroup$ – D.W. Jan 3 '17 at 5:25