V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
feigle
V2EX  ›  程序员

一个关于套料算法的问题,有人做过吗,大佬们请赐教

  •  
  •   feigle · 2019-12-25 09:38:40 +08:00 · 2617 次点击
    这是一个创建于 1777 天前的主题,其中的信息可能已经有所发展或是发生改变。

    车间制作工艺品都是 500cm×300cm 的矩形材料,现在有用户下单:需要一堆不同尺寸的小矩形材料,我需要在 500cm×300cm 的矩形材料上切割出用户需要的小矩形材料。 例如,用户需要的矩形尺寸如下(单位:cm):
    180×60,
    75×50,
    70×30,
    50×25,
    45×28
    怎么去切割 500cm×300cm 的矩形材料,使得剩余的材料为最大矩形。用户每次需要的小矩形数量和尺寸都不固定,怎么去建立模型呢,有具体算法和相关轮子吗?

    5 条回复    2019-12-25 10:34:04 +08:00
    chaoxu
        1
    chaoxu  
       2019-12-25 09:49:08 +08:00   ❤️ 1
    这种问题叫做 rectangle packing. 你可以搜一搜.
    问题本身是 NP-hard 的问题.
    zheyu
        2
    zheyu  
       2019-12-25 09:59:02 +08:00 via Android
    阿里云天池之前有个关于下料的题目,可以看看有没有人分享
    annielong
        3
    annielong  
       2019-12-25 10:11:11 +08:00
    类似集装箱装箱问题,有相关的科研论文,成品好像都是相关专业的在用,
    656711352
        4
    656711352  
       2019-12-25 10:33:33 +08:00
    http://www.vsion.cn/web/default.asp
    我们在做这一块,有需要可以交流交流
    feigle
        5
    feigle  
    OP
       2019-12-25 10:34:04 +08:00
    CSDN 上找到一个,不过也没人分享算法:<a href="https://bbs.csdn.net/topics/392494158"/>
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5542 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 107ms · UTC 06:48 · PVG 14:48 · LAX 22:48 · JFK 01:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.