乌龟塔问题 :
有 N 只乌龟，第 i 只重 Wi 克且有 Si 的力量，代表他可以负载 Si - Wi 的重量在背
上
求由这 N 只乌龟可以叠出的最大高度?
我所知道的有 2 种解法
其中一种是用动态规划，解法是 :
先对乌龟用力量由小至大去排序，然后用转移方程式
dp[i][k] = min{ dp[i-1][k], dp[i][k - 1] + Wi }
去算出答案 ( 当然 dp[i][k-1] + Wi 必须 <= Si 才是合法状态 )
上面方程式意思是 "从前 i 只乌龟中，建构 k 层塔的最小重量"
若无法建构 k 层塔则状态为 invalid
我的问题是
为什么要对力量去排序? 而不能用重量去排序再做动态规划?
我思考过后，对于重量排序我可以找到反例说明他是错误的
因为重量大的不一样要在重量小的下层
举个例子 :
编号 1 2 3 4
重量 10 20 20 140
力量 60 20 40 150
这样所可以叠出的最大高度为 2 ( 上到下 : 2 -> 3 )
但其实若是用力量去做排序
编号 1 2 3 4
重量 20 20 10 140
力量 20 40 60 150
这样所可以叠出的最大高度为 3 ( 上到下 : 1 -> 2 -> 3 )
所以这样大概可以说明为什么重量排序是不对的
因为重量大的可以在上层
那么我现在所苦恼的就是
为什么用力量排序就会是对的?
会不会有个例子是力量小的在上面结果可以让塔更高呢?
请教各位大大了QQ