Build a tallest tower by stacking the various blocks?

user_9049216 0
Viewed 2998

I came across below interview question and I am not able to understand what needs to be done here?

Suppose you are trying to build a very tall tower. You have a collection of blocks to make your tower out of. For each block type, you are given the number of blocks you have of that type, its weight, and the maximum weight that block can support above it and including itself. Suppose (for now) that all blocks have the same height (1 meter). What's the tallest tower you can construct by stacking these blocks?

Below is the example input, with each row representing a block type, of format " "

1   1  1
10  2  10
100 3  100

And the output should be: 35

What's the best way to solve this problem?

data-structures algorithm java
1 Answers

This is a variation of the knapsack problem: https://en.m.wikipedia.org/wiki/Knapsack_problem

It‘s a classical example of dynamic programming. I won‘t write down the algorithm here because countless people who are better at explaining it than I am have before me, the wikipedia article on it is certainly a good start.

user_50665670
Related