java – 这是什么算法？盒子包装/背包？
|
我昨晚正在处理一个应用程序并遇到了一个特殊的问题,我肯定可能有一个有效的算法来解决它.谁有人建议？
问题： TL; DR：也许图片会有所帮助：http://www.custom-foam-inserts.com/.我有很多适合各种隔间的物品：我想尽量减少需要采取的箱子数量. . 我有一套N件昂贵的电子设备,我想装入专门设计的保护盒中.这些盒子每个都有许多隔间,每个隔间可以装配一个物品：其中一些专门设计用于适合特定物品(即相机形孔),其中一些是通用的(矩形孔).我事先知道有不同尺寸的C隔间和尺寸. 这些盒子有两种不同的布局,每个布局至少有一个隔间.布局可能是“两个大矩形隔间和4个小圆形隔间”. 每个隔间尺寸至少存在于一个布局中,但是我的物品不适合任何隔间尺寸.每个项目至少适合一个隔间,可以放入多个不同的隔间：例如,我的DSLR相机可能紧密贴合在“中矩形”隔间中,宽松贴合在“大矩形”中,完美贴合在”单反相机隔间’,但不适合’小圆圈’.为此,我列出了哪些隔间适合每个项目. 这些物品是中度异质的 – 例如,可能有50个一个尺寸的物品和20个另一个尺寸的物品. 每个盒子有两个成本Volume和Dollars(但是D~与V成比例).我需要尽量减少这些费用中的一个或两个,同时将我的所有物品放入包装盒中.由于盒子的布局,最佳解决方案可能包含未使用的隔间.如果两个溶液具有相同的体积,请选择具有最多未使用的隔室的溶液.因为每个隔间存在于至少一个布局上并且每个物品适合于至少一个隔间,所以始终存在适合所有物品的解决方案. 项目数：< = 2000,平均情况150. 解决方法
从问题描述来看,这确实似乎是背包问题,因为你必须最大化你的可用空间,同时记住选项的重量.
根据您所使用的内容,您还可以考虑使用Genetic Algorithm.由于此问题是NP Complete,如果您需要添加更多项目,运行时间最终将会爆炸,因此如果我需要可用的最佳解决方案,我将主要使用此问题它需要的时间. 另一方面,遗传算法应该能够在相对较短的时间内提供一些解决方案,但是,它提供的解决方案可能不如Knapsack算法提供的解决方案,所以我会选择GA如果我有时间限制我需要提供一些解决方案,我不在乎它是不是绝对最好的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |