Object stacking, dynamic programming

0
votes

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.

2
algorithmdynamic-programming
I think that question belongs to cs.stackexchange.com. – user28434'mstep
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? – D.W.
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. @user28434, if you're going to suggest another site, please inform people not to cross-post (otherwise it leaves a bad experience). You can suggest they delete their question and post it elsewhere if they think it's more suitable elsewhere. – D.W.

2 Answers

2
votes

The first step to solving this problem is proving that you can find an optimal stack with boxes ordered from highest to lowest strength.

Then you just have to sort the boxes by strength and figure out which ones are included in the optimal stack.

The recursive subproblem has two parameters: find the best stack you can put on top of a stack with X remaining strength, using boxes at positions >= Y in the list.

1
votes

If good DP solution exists, it takes 2 params:

  • number of visited objects or number of unvisited objects
  • total weight of unvisited objects you can currently afford (weight of visited objects does not matter)

To make it work you have to find ordering, where placing object on top of next objects is useless. That is, for any solution with violation of this ordering there is another solution that follows this ordering and is better or equal.

You have to proof that selected ordering exists and define it clearly. I don't think simple sorting by strength, suggested by Matt Timmermans, is enough, since weight has some meaning. But it's the proofing part...