烏龜塔問題 :
有 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