我遇到了下面的面试问题,但我无法理解这里需要做什么?
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?
下面是示例输入,每一行代表一个 block 类型,格式为“”
1 1 1
10 2 10
100 3 100
输出应该是:35
解决这个问题的最佳方法是什么?
最佳答案
这是背包问题的变体: https://en.m.wikipedia.org/wiki/Knapsack_problem
这是动态规划的经典例子。我不会在这里写下算法,因为在我之前有无数比我更擅长解释它的人,关于它的维基百科文章当然是一个好的开始。
关于java - 通过堆叠各种 block 来 build 最高的塔?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56641188/