如何正确布局的网格

我具有多种不同的尺寸（宽度和高度）和具有固定大小的容器的“砖”的。我想尽可能紧凑地在容器内布置砖块，从顶部向下移动。根据前面的步骤，我已经选择了网格在任何步骤应该是最优的标准。到目前为止，我有以下（低效）代码不起作用：如何正确布局的网格

def fits?(x, y, w, h) 
    !((x + w > W) || (y + h > H)) 
end 

def overlaps?(existing, modified) 
    existing[:x] + existing[:w] > modified[:x] && existing[:y] + existing[:h] > modified[:y] && modified[:x] + modified[:w] > existing[:x] && modified[:y] + modified[:h] > modified[:y] 
end 

AXIS = :x 

W = 800 
H = 6400 

sizes = [ 
    { w: 200 , h: 200 }, 
    { w: 200 , h: 200 }, 
    { w: 400 , h: 400 }, 
    { w: 200 , h: 200 }, 
    { w: 200 , h: 200 }, 
    { w: 400 , h: 400 }, 
    { w: 600 , h: 600 }, 
    { w: 200 , h: 200 }, 
    { w: 800 , h: 800 }, 
] 

existing = [] 

sizes.each do |size| 
    size[:x] = 0 
    size[:y] = 0 

    existing.each do |existing| 

    if overlaps?(size, existing) 

     if fits?(x = existing[:x] + existing[:w], y = existing[:y], size[:w], size[:h]) 
     size[:x] = x 
     size[:y] = y 
     redo 
     end 

     if fits?(x = existing[:x], y = existing[:y] + existing[:h], size[:w], size[:h]) 
     size[:x] = x 
     size[:y] = y 
     redo 
     end 

     case AXIS 
     when :x then size[:x] = 0; size[:y] = existing[:y] + existing[:h] 
     when :y then size[:y] = 0; size[:x] = existing[:x] + existing[:w] 
     end  
    end 

    end 

    puts "#{size[:x]} , #{size[:y]} , #{size[:w]} , #{size[:h]}" 

    existing << size 
end

任何想法如何解决这个问题？看起来这将是贪婪算法的一个主要例子，但我无法弄清楚它应该是什么。

来源

2012-07-17 Stussa

你的问题是NP-Hard，从而有它没有已知的多项式的解决方案。

从Subset Sub Problem一个简单的还原可以示出：

广义子集和问题：给定一组S和整数k，当且仅当有求和到k的S一个子集返回true。

还原：给定子集和(S,k)的一个实例 - 创建尺寸(1,k)的容器中，元素是(1,s)每个s在S。

很容易看出，当且仅当您可以完全填充容器 - 原始子集和问题的解决方案是真实的，因此以上是多项式约简，问题是NP-Hard。（注意：“让它尽可能紧凑”的原始问题实际上是这个问题的优化问题，并且仍然是NP-Hard）。

对不起，这个坏消息。
一些替代使用指数溶液（如backtracking），启发式或近似算法。
注意，在1个维空间，这个问题有一个pseudo-polynomial solution，使用动态编程，但我不认为它可以在2维空间平凡应用（如果有的话）。

来源

2012-07-17 05:55:11 amit

正如已经由阿米特指出的那样，你的问题是NP难问题。但是，这不应该阻止你简单地遍历砖块的所有排列，并且看看它们中哪一个最适合。也就是说，你没有“太多”砖块。

的价值“太多”，主要取决于你的计算速度和可用的时间，但我的猜测是，值高达，比方说，14都是精品。

如果蛮力解决方案被证明是太慢了，你仍然可以尝试试探或近似算法。

编辑：你的例子砖显得很做作。你的砖尺寸是否服从某些标准，还是完全武断？也许你可以利用对砖块大小的限制，如果有的话。

来源

2012-07-17 08:41:22 Philip

如何正确布局的网格

回答

相关问题