将二维盒子排序放入更大的盒子中,以最有效和完整的方式填充。

背景:

大家好,我一直在尝试编写一个函数,但是我卡住了。我的最终目标是创建一个应用程序,用户输入大盒子和一组小盒子(都是二维的)。程序会处理数据,尽可能地用小盒子填满大盒子。如果你想知道,这是为剧院舞台应用程序设计的。

代码部分:

我有一个函数,输入参数是“box”(由用户创建的大盒子列表)和“platforms”(小盒子列表)。正如注释中所示,如果小盒子完全符合大盒子,那么已经编写好了填充代码的程序。然后程序会减少该规格平台的数量,并将该盒子标记为已填满。

问题:

我无法编写一个程序,以最高效的方式将两个小盒子放入一个大盒子中。我考虑了使用大盒子的x轴填充给定一组小盒子的x值,然后在具有相同x值但具有不同y值的不同小盒子之间进行交替,但是存在几个问题。

你们有什么建议吗?

userInterfaceCall()
    squares[#squares+1] = {x1=x, y1=y, x2 = nil, y2 = nil, f=false}
    -- x1,y1和x2,y2是正方形的两个对角点的坐标
    -- f是布尔值,用于表示正方形是否填满
end

platforms[1] = {x=4, y=4, q=2} --示例用户数据
platforms[2] = {x=4, y=6, q=2} --x和y是平台尺寸
platforms[3] = {x=6, y=2, q=1} --q是数量
platforms[4] = {x=8, y=4, q=1}

process(squares,platforms) -- 这是由一个UI元素调用的

function process(box,platforms)
for i,box in ipairs(box) do               -- 对于每个正方形
    if box.f == false then                -- 如果方格已经有了已给出的平台,则不执行任何操作
        for i,platform in ipairs(platforms) do    -- 对于每个平台
            boxX = math.abs(box.x1-box.x2)/scale  -- 忽略这一行,这是从
            boxY = math.abs(box.y1-box.y2)/scale  -- 像素大小到英尺大小的比率
            if boxX == platform.x and boxY == platform.y and platform.q > 0 then    -- 测试任何一个平台是否能直接放入盒子中
                placements[#placements+1] = {x1 = box.x1, y1 = box.y1, x2 = box.x2, y2 = box.y2, s = ''} -- 创建新的放置位置
                platform.q = platform.q - 1       -- 数量减少
                box.f = true                 -- 填完盒子了
            elseif boxY == platform.x and boxX == platform.y and platform.q > 0 then  -- 测试交换x和y
                placements[#placements+1] = {x1 = box.x1, y1 = box.y1, x2 = box.x2, y2 = box.y2, s = ''}
                platform.q = platform.q - 1
                box.f = true
            elseif
                -- 将多个平台放入一个盒子,请帮忙
            else
                setPrompt('Could not find for box: '..boxX..','..boxY)
            end
        end
    end
end 
点赞
用户2765603
用户2765603

你遇到了一个多维背包问题的变体,该问题已知为NP完全问题。因此,没有简单的“最佳”解决方案,但已找到一些策略可在可接受的时间内得出可接受的结果。请参见链接的文章以获取更进一步的解释。

2015-05-27 05:53:19
用户1224973
用户1224973

对于其他人来说,可以在这里阅读:http://codeincomplete.com/posts/2011/5/7/bin_packing/

这是一个能够工作的 JavaScript/CSS 解决方案。

2015-05-28 00:44:49