Построить самую высокую башню, сложив различные блоки?

Question

Я наткнулся ниже на вопрос интервью, и я не могу понять, что здесь нужно сделать?

Предположим, вы пытаетесь построить очень высокую башню.У вас есть коллекция блоков, из которых вы можете сделать свою башню.Для каждого типа блока вам дается количество блоков этого типа, его вес и максимальный вес, который блок может выдержать над ним, включая самого себя.Предположим (пока), что все блоки имеют одинаковую высоту (1 метр).Какую самую высокую башню вы можете построить, сложив эти блоки?

Ниже приведен пример ввода, где каждая строка представляет тип блока в формате ""

1   1  1
10  2  10
100 3  100

Ивывод должен быть: 35

Как лучше всего решить эту проблему?

Answer 1

Это вариант проблемы с рюкзаком: https://en.m.wikipedia.org/wiki/Knapsack_problem

Это классический пример динамического программирования. Я не буду здесь описывать алгоритм, потому что бесчисленное множество людей, которые лучше его объясняют, чем я, до меня, статья в Википедии об этом, безусловно, хорошее начало.

Answer 2

Условие, что все блоки имеют одинаковую высоту, позволяет решить эту проблему с помощью жадного метода.
Просто продолжайте добавлять самые легкие блоки под рукой, пока вы не исчерпаете их или не превысите общий вес, который может выдержать такой тип блока.
Вы можете думать об этом, как о строительстве башни сверху, используя более тяжелые части внизу.