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

一个算法问题,应该是动态规划的。

  •  
  •   zjty · 2020-12-01 15:10:55 +08:00 · 881 次点击
    这是一个创建于 1213 天前的主题,其中的信息可能已经有所发展或是发生改变。

    就是一个固定尺寸的平面比如 7050,然后有一个小的平面 xy,然后在这个固定平面上能放置多少个这样的小平面。

    第 1 条附言  ·  2020-12-02 09:48:51 +08:00
    早上想到一个方法不知道是否可行,比如一个 90*71 的平面,拿 25*20 的小平面去覆盖,我去比对最短边的效率问题,用 71 对 25,20,25+20,[25+20]+ 25,[25+20]+ 20 来取模,选择模最小的先去覆盖,直到取满,之后将剩下的空余面积重复以上计算,直到排不下就是最大的数量,欢迎大家探讨下是否合理
    第 2 条附言  ·  2020-12-02 12:32:45 +08:00
    组合是不定的,穷举不完,发现可以 20+20+20+25 这些,所以要全枚举比对
    第 3 条附言  ·  2020-12-02 15:52:33 +08:00
    参照其上的逻辑精简后,用了贪心算法,应该是对的。
    5 条回复    2020-12-03 09:28:40 +08:00
    dilu
        1
    dilu  
       2020-12-01 18:29:36 +08:00
    你是想说,有个平面是 70*50,然后小平面 x*y 。这个平面上最多能容纳多少个小平面?
    zjty
        2
    zjty  
    OP
       2020-12-02 08:40:44 +08:00
    @dilu 是的,有思路么,我想了一下午,没想出思路来,不是个正方形,中间的缺口问题。
    cczeng
        3
    cczeng  
       2020-12-02 11:21:11 +08:00
    应该是动态规划,背包问题和这个差不多。
    zjty
        4
    zjty  
    OP
       2020-12-02 11:54:11 +08:00
    @cczeng 有具体的思路么,很久不写算法了,感觉和背包问题还是有些差别
    kb5000
        5
    kb5000  
       2020-12-03 09:28:40 +08:00 via Android   ❤️ 1
    二维装箱问题,应该只能近似
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5303 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 09:22 · PVG 17:22 · LAX 02:22 · JFK 05:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.