題目的原型應該是 01 背包問題，只是原本的重量限制變成了力矩限制。

雖然可以 GOOGLE 到解法( 感謝 傑克的程式區 的說明 )，但是對於解法說明我還是一知半解。

我自己的認知是既然是從 01 背包問題演變而來，那解法的部分應該也是：

在 01 背包問題解法的一維陣列實作時是枚舉所有的重量，陣列存的值是當重量＝陣列位置時可獲得的最大價值

對應到這題給的限制是力矩，力矩＝長度Ｘ重量，所以這題會改為枚舉兩個維度：長度和力矩

更新方式也是從由大往小更新，所以套用到二維上自然也是長度和力矩各自由大到小更新。

只是在處理 01 背包時並不會做排序後從重量最重開始更新陣列，但這題的做法卻是必須的？！

傑克的程式區的說明：希望體積越重的物品放在離支撐點越近的地方，這個說明是對的但不足以說明排序是必須的

如果不排序就直接去更新二維陣列得到錯誤的答案，自己手動產生兩筆小測資對於有無排序都不受影響，

想問一下其他有解開或是看懂解法的大大們對於排序是必然的說明，先謝謝各位的回覆。

附上[該題網址](https://allem40306.github.io/blog/posts/3b76/]

題目的原型應該是 01 背包問題，只是原本的重量限制變成了力矩限制。

雖然可以 GOOGLE 到解法( 感謝 傑克的程式區 的說明 )，但是對於解法說明我還是一知半解。

我自己的認知是既然是從 01 背包問題演變而來，那解法的部分應該也是：

在 01 背包問題解法的一維陣列實作時是枚舉所有的重量，陣列存的值是當重量＝陣列位置時可獲得的最大價值

對應到這題給的限制是力矩，力矩＝長度Ｘ重量，所以這題會改為枚舉兩個維度：長度和力矩

更新方式也是從由大往小更新，所以套用到二維上自然也是長度和力矩各自由大到小更新。

只是在處理 01 背包時並不會做排序後從重量最重開始更新陣列，但這題的做法卻是必須的？！

傑克的程式區的說明：希望體積越重的物品放在離支撐點越近的地方，這個說明是對的但不足以說明排序是必須的

如果不排序就直接去更新二維陣列得到錯誤的答案，自己手動產生兩筆小測資對於有無排序都不受影響，

想問一下其他有解開或是看懂解法的大大們對於排序是必然的說明，先謝謝各位的回覆。

如果你只是要測資的話

2 4 2

1 1

2 1

最佳解是第二個物品放第一格 第一個物品放第二格 答案為2

至於原因 有點貪心的成分

首先要知道背包的dp解法有個問題就是: 在後面被考慮到的物品肯定得在前面的物品後面(才符合dag)

然而有時候(例如上面測資) 後面的物品一定得在前面才比較好 至於條件如下

考慮兩個重量為ma mb的物品 假設ma<=mb 且a肯定在b的前面

則獲得力矩為vama + vbmb (va < vb)

但如果交換順序 vamb+vbma

拿去減(vamb+vbma) - (vama+vbmb) = va(mb - ma) + vb(ma - mb) = (mb - ma)(va - vb)

由於ma-mb >= 0且va-vb < 0 因此交換後-交換前 <= 0 也就是交換後的力矩肯定不會比交換前的力矩大