sinat_38913556
2018-03-27 07:17
采纳率: 91.4%
浏览 837
已采纳

一个算法该如何实现呢

需要生产3种型号的部品(A,B,C),这三种型号的长度为A=562.6mm,B=362.6mm,C=237.6mm,不考虑刀的损失长度。一根材料长度为2743mm。
要生产A180个,B217个,C220个,怎么切,最终使用的材料根数最少。最少为多少根?

比如:方案1,A1个,B4个,C3个,切53根;
方案2,A4个,B0个,C2个,切28根
方案3,A3个,B1个,C1个,切5根;
合计86根。

如何设计这个算法呢

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • qq_30866867 2018-03-27 08:36
    已采纳

    暴力破解ok吗?

    1.获取边界值 (180*562.6 + 362.6*217 + 237.6*220) / 2743 向上取整.得到边界个数MIN,MAX.
    2.列举出所有的有效方案(保证不浪费材料的前提),如上.有M个方案
    3.设置M个变量i,j,k....,代表不同方案的根数.且根数总和 >= MIN
    4.嵌套循环,最外层控制总根数N, 每次循环总根数N++.
    5.里层循环对应的总根数要等于N, 直至找到满足A,B,C个数>= 180,217,220为止最小的根数,跳出循环. 有问题请指正,谢谢!

    打赏 评论
  • 红帽01 2018-03-27 07:53

    感觉像2个背包问题。

    第一个背包问题
    用一根材料生产3个部品,得到一个最佳生产方案。
    比如(A2个,B4个,C3个),按次方案生产。能够得到剩余的2个部品。

    第二个背包问题
    用一根材料生产剩余的2个部品,得到一个最佳生产方案。
    比如(B4个,C4个),按次方案生产。能够得到剩余的1个部品。

    最后全部生产剩余的1个部品。

    打赏 评论
  • studylearnjava 2018-03-27 08:18

    第一步 根据材料长度2743
    计算出n种方案 如 方案1( A:1, B:4, C:3)

    第二步 根据生产的A 180, B 217, C 220
    使用各种方案的排列组合 保存排列组合 总和最小的那个

    萌新弱弱的问一句 需要用什么语言实现

    打赏 评论
  • 洋洋不得意 2018-03-27 08:30

    1.列举出一根材料最多能做几根所需要的,把方案做出来,假如是aabc
    2.然后就按照此方案开始做,直到某一根完成
    3.重复第一步
    试试这个?

    打赏 评论
  • a414878523 2018-04-10 18:31

    动态规划
    记f[i,j,k]表示A生产i个,B生产j个,C生产k个需要的最少根数
    那么f[i,j,k]=min{f[i - x1, j - x2, k - x3] + 1}
    表示这一根生产了x1个A,x2个B,x3个C,枚举所有的满足能用一根生产的x1,x2,x3
    初始值为f[0,0,0]=0
    最后答案为f[180, 217, 220]
    因为不是所有状态都有用,所以如果使用记忆化搜索效果应该会更好

    打赏 评论

相关推荐 更多相似问题