[問題] 請問更好的解法

[allen7812 (allen)]

大家好

最近遇到一個問題想請問

題目：

有N個物件a1、a2...an，各有重量w1、w2...wn，以及組合重量限制W
要如何組合a1等物件，使得所有物件都被挑選到，且各組合重量不超過W，但須盡量逼近W
，以及組合數量為最少?

EX:有10個物件物件，重量分別是2、2、2、2、2、8、8、8、8、8，組合重量限制10，最
佳解是 (2 + 8) * 5，總共有5包，錯誤解則是 2*5、8、8、8、8、8 總共有6包。


目前與朋友討論如下：

把重量排續依序為w1...wn

從最大的w1開始尋找可能的組合

ex. w1-w2-w5 w1-w3-w6-w7

再挑出浪費重量最小的

ex. w1-w2-w5浪費2kg w1-w3-w6-w7 浪費1kg 則把w1,w3,w6,w7，包成一包

再依序反覆執行這動作


這樣寫是否只要用DP從最大的重量開始尋找可能組合，就可以把問題解出?

謝謝



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.201.212
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1475843024.A.AA1.html
推 FRAXIS: 這是 bin packing 嗎？
→ allen7812: 好像是，感謝幫忙
推 s89162504: 課本上有2近似算法
推 DJWS: 樓上講的是哪本課本?
推 LPH66: 看維基百科, 簡單的任意取物看到有空間就放就是 2 近似
推 DJWS: 因為印象中沒有在書上看過，所以才問的
→ DJWS: 剛剛發現[CLRS]三版習題35-1有提到
→ pttworld: 這排序是語法的加速。