[問題] 請問更好的解法
看板Prob_Solve (計算數學 Problem Solving)作者allen7812 (allen)時間8年前 (2016/10/07 20:23)推噓5(5推 0噓 3→)留言8則, 6人參與討論串1/1
大家好
最近遇到一個問題想請問
題目：
有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
推
10/07 21:30, , 1F
10/07 21:30, 1F
→
10/07 21:51, , 2F
10/07 21:51, 2F
推
10/07 23:42, , 3F
10/07 23:42, 3F
推
10/08 07:16, , 4F
10/08 07:16, 4F
推
10/08 18:30, , 5F
10/08 18:30, 5F
推
10/09 07:19, , 6F
10/09 07:19, 6F
→
10/09 07:20, , 7F
10/09 07:20, 7F
→
10/11 08:27, , 8F
10/11 08:27, 8F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
