CODEWITHSUNDEEP
algorithm
MonkeyBusiness
MonkeyBusiness

Reputation: 163

Block Stacking Algorithim

I am pretty sure this simple problem has a proper name but I have no idea what it is.

I have a number of blocks of different widths (all same height).

I would like to stack these blocks horizontally such that the width of the row does not exceed a predefined Max Width constant. If at any moment placing a new block makes the width of the row exceeds the maximum, the block is removed and put on a new row.

Is there an algorithm for optimal stacking of the blocks such that the number of rows is minimum?

What is the name of this problem and how to solve it?

Upvotes: 0

Views: 369

Answers (1)

Nilesh Adhikari
Nilesh Adhikari

Reputation: 38

Here is an algorithm in java that can achieve what you want, although u may have to tweak and edit this alot.

 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);
}

And here is the output of that above code.

[[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], [], [] , [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

Few notes on how i made this algorithm work

  1. The maximum width is 100
  2. The stack of blocks are stored in 2 dimensional Arraylist. Lowest stack of block is Array[0][], then Array[1][] ...... and so on.
  3. The blocks with given weight are produced by a for loop which adds value of i by 1 (from i = 0) and only works while temporarySumOfWidth is less than 100 and currentHorizontalLogOfBlock is less than 100(2 dimensional array with first dimension as 100)
  4. The blocks are stacked in place until 'i' becomes greater than 100, which means that you cannot stack a block whose width is greater than 100 if the limit is 100.

This is not perfect so please write any queries you may have.

Upvotes: 1

Related Questions