作者allen7812 (allen)
看板Prob_Solve
标题[问题] 请问更好的解法
时间Fri Oct 7 20:23:40 2016
大家好
最近遇到一个问题想请问
题目：
有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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1475843024.A.AA1.html
1F：推 FRAXIS: 这是 bin packing 吗？ 10/07 21:30
2F：→ allen7812: 好像是，感谢帮忙 10/07 21:51
3F：推 s89162504: 课本上有2近似算法 10/07 23:42
4F：推 DJWS: 楼上讲的是哪本课本? 10/08 07:16
5F：推 LPH66: 看维基百科, 简单的任意取物看到有空间就放就是 2 近似 10/08 18:30
6F：推 DJWS: 因为印象中没有在书上看过，所以才问的 10/09 07:19
7F：→ DJWS: 刚刚发现[CLRS]三版习题35-1有提到 10/09 07:20
8F：→ pttworld: 这排序是语法的加速。 10/11 08:27