Problem with turtle tower variation / Dynamic Programming

5
votes

So I have a problem with DP, as I'm a beginner. Here's my problem, it's like the turtle tower but with some changes, as it has values for each turtle too.

You are given n turtles, and for each turtle you are given its weight (w) its strength (s) and its value(v). The strength of a turtle is the maximal weight you can put on it without cracking its shell. Find the greatest possible value you can get out of turtles, by stacking one on top of the other without cracking any turtle.

I'm having trouble with the recurrence relation, since I'm confused with the fact that I'd have to check whether the sum of weights on top of each turtle is higher than its strength. I mean, I thought about making an array holding the best tower value for each next turtle we add to the tower, but I don't know how I'm going to check whether all the turtles under the new one can hold the new sum of weights with their strength.

The only way I could think about is saving each turtle's strength minus current_sum_of_weights of turtles on top of her. But it seems too complicated.

I guess I would start by sorting turtles based the sum of each one's weight and strength but still I'm having trouble with the recursion.

I don't need to write a code, I just want to write the recurrence relation and prove it.

2
algorithmdynamic-programming
You need to show us your exact thought process or code in order to enable us to help you with your specific problem. – Lajos Arpad
@LajosArpad better now? – Littlish
You state that you are having trouble with recursion. This problem is not necessarily solved by recursion, so, the fact that you are having trouble with that begs the question: what is the exact trouble? We can of course solve this problem, but we would like to help you solve it. To achieve that we need to understand the exact cause of which you are stuck at this point. – Lajos Arpad
@LajosArpad All I can think about is an array V containing the best value until turtle i, if s>=w_i: V[i][s]=max{V[i-1][s]+v_i, V[i-1][c]), where i stands for the last turtle between T1...Tn, s for the minimum strength of the tower right now and v_i the value of the i-th turtle. But s should be something like s=min{s_i, s-w_i) Unfortunately I cant figure out how to include this to the previous relation. – Littlish
@Littlish I have to go now, I will respond tomorrow (if I do not forget to do so) – Lajos Arpad

2 Answers

1
votes

You need to optimize value and you are right in stating that sorting turtles by strength helps. We could start by sorting by weight or by value instead, but sorting by strength as a first step makes slightly more sense, because this way you will see what's possible rather than what's desired. However, weight is also part of the possibility, so s * w makes even more sense as a sorting criteria, as you want to put the most massive (weighty and strong) turtles into the bottom of your tower and the weakest turtles into the top.

Since you have to find out the very best solution, it makes sense to compute all seemingly feasible solution with a divide et impera implementation for this task and to avoid having to evaluate provably worse alternatives, always prune candidate variations when they are provably worse than the current solution.

If w1 <= w2 and s1 <= s2 and v1 < v2, then turtle1 is provably worse as an alternative to turtle2, because it has a smaller value and by preferring turtle1 we will not even be compensated due to turtle2 being more massive.

So, when you find the first turtle that you can use, you search for alternatives, which have more strength, weight or value. Due to the suggested ordering higher indexed values will seldomly have higher weight or strength, but that's still possible.

1
votes

Let f(i, v) represent the weight of the lightest tower of value v up to the ith tower, where the towers have been ordered by weight + strength ascending. Then:

f(i, v) = min(
  f(i - 1, v),
  weight(i) + f(i - 1, v - value(i))
     if strength(i) ≥ f(i - 1, v - value(i)) else Infinity
)

To explain the ordering trick, as described in COMP3121/9101/3821/9801 Lecture Notes; More on Dynamic Programming (DP); LiC: Aleks Ignjatovic; School of Computer Science and Engineering; The University of New South Wales; Sydney, Australia:

We'd like to prove that we can rearrange any legitimate tower to be ordered by weight + strength ascending. To do this we need to show that any consecutive pair where

(1) strength(t_i+1) + weight(t_i+1) < strength(t_i) + weight(t_i)

can be legitimately swapped, since then we could apply bubble sort. In other words, that

(2) (Sum j=1...i−1 of weight(t_j)) + weight(t_i+1) < strength(t_i)

The original, legitimate tower has

(3) (Sum j=1...i−1 of weight(t_j)) + weight(t_i) ≤ strength(t_i+1)

Add weight(t_i+1) to both sides:

(4) (Sum j=1...i−1 of weight(t_j)) + weight(t_i) + weight(t_i+1) ≤ strength(t_i+1) + weight(t_i+1)

Substitute (1) for the right side:

(Sum j=1...i−1 of weight(t_j)) + weight(t_i) + weight(t_i+1) ≤ strength(t_i) + weight(t_i)

Cancel weight(t_i):

(Sum j=1...i−1 of weight(t_j)) + weight(t_i+1) ≤ strength(t_i)