您有n1个大小为s1的项目,n2个大小为s2的项目,以及n3个大小为s3的项目.您希望将所有这些项目打包到每个容量为C的容器中,以便最大限度地减少使用的容器总数.
我们如何使用最少数量的垃圾箱实现解决方案？贪婪不一定有效.
小智 6
这不是一个愚蠢的问题,IMO.
通常,Bin填料已知为NP-Complete.
但是你的情况,具有固定数量的对象权重的Bin打包是一个有趣的变体.
以下论文声称有一个多项式时间算法,当你允许3种不同的大小时,它会带来最优的1:http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310.(警告:我只是抽象的).
所以我猜这个版本也是NP-Hard,而Greedy算法可能无法正常工作.不太确定动态编程(bin打包是NP-Complete).
希望有所帮助.