问海龟塔变化/动态规划问题

EN

让f(i, v)表示最轻的v值塔的重量，直到i第四塔，在那里，这些塔是由weight + strength上升命令的。然后：

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
)

解释排序技巧，如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中所述

我们想证明，我们可以重新安排任何合法的塔被weight + strength升序。要做到这一点，我们需要展示任何连续的一对

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

可以合法交换，从那时起我们就可以应用泡沫分类了。换句话说，

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

原来合法的塔楼

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

将weight(t_i+1)添加到双方：

(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)

以(1)代替右侧：

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

取消weight(t_i)

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

你需要优化价值，并且你正确地说，根据力量分类海龟是有帮助的。我们可以从按重量或值进行排序开始，但作为第一步，按强度进行排序更有意义，因为这样您将看到什么是可能的，而不是所希望的。然而，重量也是可能性的一部分，所以s*w作为分类标准更有意义，因为你想把最庞大(重和强壮)的海龟放在塔底，把最弱的海龟放到顶部。

既然你必须找出最好的解决方案，就有必要为这项任务计算所有看似可行的解决方案，并且避免不得不评估明显更糟糕的备选方案，当候选方案比当前解决方案糟糕得多时，总是对它们进行修剪。

如果w1 <= w2和s1 <= s2和v1 < v2，那么turtle1作为turtle2的替代物显然更糟糕，因为它的值较小，而通过选择turtle1，甚至不会因为turtle2更大而得到补偿。

所以，当你找到你可以使用的第一只海龟时，你就会寻找其他的选择，它们的强度、重量或价值都会更高。由于建议排序，较高的索引值将很少有更高的重量或强度，但这仍然是可能的。