大家好
最近遇到一個問題想請問
題目:
有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從最大的重量開始尋找可能組合,就可以把問題解出?
謝謝