时间戳

首页 > 解决方案 > 块堆叠算法

algorithm - 块堆叠算法

问题描述

我很确定这个简单的问题有一个正确的名称，但我不知道它是什么。

我有许多不同宽度的块（高度相同）。

我想水平堆叠这些块，使行的宽度不超过预定义的 Max Width 常数。如果在任何时候放置一个新块使行的宽度超过最大值，则该块被移除并放在一个新的行上。

是否有一种算法可以优化块堆叠以使行数最少？

这个问题的名称是什么以及如何解决？

标签： algorithm

解决方案

这是Java中的一种算法，可以实现您想要的，尽管您可能需要对其进行大量调整和编辑。

 public static void main(String[] args) {
    int maxWidth=100;
    int i;
    ArrayList<ArrayList<Integer>> serialBlocksData = new ArrayList<>(100);
    int temporarySumOfWidth;
    temporarySumOfWidth=0;
    int currentHorizontalLogOfBlock=0;
    for(i=0; i < 100; i++) {
        serialBlocksData.add(new ArrayList());
    }
    for(i=0;(temporarySumOfWidth<maxWidth&&currentHorizontalLogOfBlock<100);i++){
        if((temporarySumOfWidth+i)>=maxWidth){
            currentHorizontalLogOfBlock=currentHorizontalLogOfBlock+1;
            temporarySumOfWidth=0;
            serialBlocksData.get(currentHorizontalLogOfBlock).add(i);
            temporarySumOfWidth=temporarySumOfWidth+i;
        }else{
            serialBlocksData.get(currentHorizontalLogOfBlock).add(i);
            temporarySumOfWidth=temporarySumOfWidth+i;
        }
    }
    System.out.println(serialBlocksData);
}

这是上面代码的输出。

[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [14, 15, 16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26], [27, 28, 29], [30, 31, 32], [33, 34], [35, 36], [37, 38], [39, 40], [41, 42], [43, 44], [45, 46], [47, 48], [49, 50], [51], [52], [53], [54], [ 55]、[56]、[57]、[58]、[59]、[60]、[61]、[62]、[63]、[64]、[65]、[66]、[67] , [68], [69], [70], [71], [72], [73], [74], [75], [76], [77], [78], [79], [ 80]、[81]、[82]、[83]、[84]、[85]、[86]、[87]、[88]、[89]、[90]、[91]、[92] , [93], [94], [95], [96], [97], [98], [99], [100], [], [], [], [], [], [] , [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [ ], [], [], [], [], [], [], [], [], [], [], [], []]

关于我如何使这个算法起作用的几点说明

  1. 最大宽度为 100
  2. 块堆栈存储在二维 Arraylist 中。最低堆栈的块是 Array[0][]，然后是 Array[1][] ......等等。
  3. 具有给定权重的块由 for 循环生成，该循环将 i 的值加 1（从 i = 0），并且仅在 temporalSumOfWidth 小于 100 且 currentHorizo​​ntalLogOfBlock 小于 100 时有效（二维数组，第一维为 100）
  4. 积木在原地堆叠，直到 'i' 大于 100，这意味着如果限制为 100，则不能堆叠宽度大于 100 的积木。

这并不完美，所以请写下您可能有的任何疑问。

推荐阅读