-2
$\begingroup$

when we are trying to solve a problem with dynamic programming. we have to follow some general steps

  1. characterize the solution structure
  2. Recursively define optimal solution
  3. compute the value from bottom up fashion

Can anyone briefly explain the steps for this problem scenario. we need a 444 meter rope. but we have only small pieces of ropes. then we have to find out the minimum number of pieces of rope needs to construct that large rope.

Length---->Quantity

  • 50m--->10
  • 45m--->12
  • 30m--->3
  • 8m---->12
  • 3m---->2
  • 2m---->2
$\endgroup$
  • $\begingroup$ In the guideline, you should also make sure that you store the sub-solutions appropriately. I think the more important thing is making sure you characterize the problem so that you don't end up doing brute force search. $\endgroup$ – InformedA Oct 8 '14 at 20:33
  • $\begingroup$ Do you need exactly or at least 444 meters? $\endgroup$ – Yuval Filmus Oct 9 '14 at 1:10
  • $\begingroup$ you just glue them, end-to-end, or do you lose some length for putting them together? - can you cut them? $\endgroup$ – babou Oct 9 '14 at 17:14
  • $\begingroup$ need exactly 444 metres and we can't cut the ropes $\endgroup$ – Canon Oct 10 '14 at 5:36
  • $\begingroup$ This is the subset sum problem. $\endgroup$ – Raphael Oct 10 '14 at 12:02
1
$\begingroup$

The Wikipedia page to the Knapsack Problem has a nice explanation of a dynamic programming algorithm for it:

http://en.wikipedia.org/wiki/Knapsack_problem

The knapsack problem is very similar to your problem - just define length of rope to be equal to their "weight" and use a uniform cost for all of them.

$\endgroup$

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.