algorithm - 龟塔变异问题/动态规划

Question

所以我有 DP 问题，因为我是初学者。
这是我的问题，它就像乌龟塔，但有一些变化，因为它也有每只乌龟的值。

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.

我在递归关系方面遇到了麻烦，因为我对我必须检查每只乌龟顶部的权重总和是否高于其强度这一事实感到困惑。
我的意思是，我考虑过为我们添加到塔中的每只下一个海龟创建一个包含最佳塔值的数组，但我不知道我将如何检查新海龟下的所有海龟是否可以容纳新的总和重量与他们的力量。

我能想到的唯一方法是保存每只海龟的力量减去她身上海龟的 current_sum_of_weights 。但是好像太复杂了。

我想我会首先根据每个人的体重和力量的总和对海龟进行排序，但我仍然在递归方面遇到问题。

我不需要写代码，我只想写递归关系并证明它。

Answer 1

你需要优化值(value)，你说按强度排序海龟是正确的。我们可以从按重量或按值排序开始，但按强度排序作为第一步更有意义，因为这样你会看到什么是可能的，而不是你想要什么。但是，重量也是可能性的一部分，因此 s * w 作为排序标准更有意义，因为您希望将最大(重量和强壮)的海龟放入塔的底部，而将最弱的海龟放入塔的顶部.

由于您必须找出最好的解决方案，因此使用divide et impera 实现来计算所有看似可行的解决方案是有意义的，并避免必须评估可证明更糟的替代方案，当它们可证明比当前的解决方案。

如果 w1 <= w2 and s1 <= s2 and v1 < v2，那么turtle1作为turtle2的替代品显然更糟糕，因为它具有较小的值，并且由于turtle2更大，我们更喜欢turtle1我们甚至不会得到补偿。

因此，当您找到可以使用的第一只海龟时，您会寻找具有更大强度、重量或值(value)的替代品。由于建议排序，较高的索引值很少会具有较高的重量或强度，但这仍然是可能的。