当前位置: 代码迷 >> C# >> ,最优组合算法有关问题
  详细解决方案

,最优组合算法有关问题

热度:99   发布时间:2016-05-05 02:38:23.0
求助,最优组合算法问题
各位大神,我在开发中碰到了这样的问题,有数种商品,商品的价值不等,要将商品进行打包包装,一个包装盒只能不超过99万价值的商品,如何用最少的包装盒包装最多价值的商品。
示例:A商品:10万、B商品:10万、C商品:20万、D商品:20万、E商品:60、F商品:60万
正解:使用2个包装盒,包装盒1【A、C、E】 、包装盒2【B、D、F】

这样的案例用什么算法实现呢?
------解决思路----------------------
引用:
Quote: 引用:

把商品价值从大到小排列
拿出一个盒子,按顺序尝试将商品塞进去,直到盒子塞满或者所有商品遍历完毕
重复上一步直到所有商品装完


用我给的那个例子看,这样不行,会用掉3个包装盒,结果可能会是这样:
包装盒1【F-60万】、包装盒2【E-60万】、包装盒3【D-20万、C-20万、B-10万、A-10万】

不能满足需求呢,有没有这方面的其他思路呢?

楼主你智商太低,我说详细点

把商品价值从大到小排列
    F E D C B A

拿出一个盒子,按顺序尝试将商品塞进去,直到盒子塞满或者所有商品遍历完毕
    盒子1,价值99
    先F,可以装下,现在盒子里有F,剩余价值39
    E,装不下了,跳过
    D,可以装下,现在盒子里有F、D,剩余价值19
    C,装不下,跳过
    B,可以装下,现在盒子里有F、D、B,剩余价值9
    A,装不下

重复上一步直到所有商品装完
拿出一个盒子,按顺序尝试将商品塞进去,直到盒子塞满或者所有商品遍历完毕
    盒子2,价值99
    先E,可以装下,现在盒子里有E,剩余价值39
    C,可以装下,现在盒子里有E、C,剩余价值19
    A,可以装下,现在盒子里有E、C、A,剩余价值9

完了
  相关解决方案