CODEWITHSUNDEEP
javaalgorithmdata-structures
flash
flash

Reputation: 1519

Build a tallest tower by stacking the various blocks?

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?

Upvotes: 3

Views: 3546

Answers (1)

xXliolauXx
xXliolauXx

Reputation: 1313

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.

Upvotes: 2

Related Questions