[100分]背包问题的算法（思路易可）

已知：有无限个标准背包B,容量为B[Max] 
    还有剩余背包B[1],B[2]....B[N]个，其剩余容量分别为R[1],R[2]...R[N]
    现有物品W[1],W[2]....W[N]个，其体积为V[1],V[2]...V[N]，个数为A[1],A[2]...A[N]
求：一方案将所有的物品都装进背包且要求用于装物品的背包的剩余空间最少。 


PS：不是求近似的最优解，而是直接求最优解的算法，而且算法不能太耗时，应为单件物品的数量可能在1k或以上，剩余背包的数量也是很多的。

11 个解决方案

#1

http://blog.csdn.net/newflypig/archive/2007/10/20/1834716.aspx

#2

标准的动态规划问题

#3

背包问题九讲，这个是我见过的最好的了，应该不会让你失望。

http://www.concretevitamin.com.cn/informatics/Pack/Index.html

#4

资源很好，谢谢！！！！

#5

发现5，6， 9，附录二这几章不能看

这里有人转载了：
http://hi.baidu.com/acmgood/blog/category/%B1%B3%B0%FC%CE%CA%CC%E2%BE%C5%BD%B2

五：
二维费用的背包问题
六：
分组的背包问题
九
背包问题问法的变化
附二：
背包问题的搜索解法

引用 3 楼 novice2008 的回复:

背包问题九讲，这个是我见过的最好的了，应该不会让你失望。 

http://www.concretevitamin.com.cn/informatics/Pack/Index.html

#6

用动态规划应该可以解,不过感觉复杂度不低呢!

看看大家都有什么好的方法吧!其实感觉已经不是背包问题了,更像拼图问题!

#7

本身就是NP难的问题，如果问题规模很大，执意求最优解效率会很低。
换句话说，这么多人研究近似解也是不得已而为之的法子。真有你期望得这么理想:效率飞快而且最优，*才不用啊！

#8

要最优解 回溯 否则 近似解

#9

多谢各位的鼎力相助，我也不妨直说，其实这是一个玻璃切割排版的程序，基本上如何判断切割方案是否能行，如何去执行该切割方案我已经搞定了，差的就是如何去把可能的解模拟出来，原本我做出来的就是将所玻璃组合都模拟出来，再每个去执行判断，把剩余面积最小的组合拿来作最优的解，但是我发现模拟一个元素个数为20的一维数组就要用好长的一段时间，更不用说要去实行判断可否行了！所以我求各位大哥，帮忙找找或者介绍一些方法或算法能减少其耗时的

#10

总体思路还是回溯 根据具体的细节进行剪枝.

#11

引用 10 楼 yelling 的回复:

总体思路还是回溯 根据具体的细节进行剪枝.

可以具体点吗？