pro.algorithms
Ещё такой вопрос, возможно тривиальный и кто-то сталкивался, нужен алгоритм,
который проверяет, можно ли из заданного массива натуральных чисел N, длины l, представить какое-то число x - как сумму его элементов?
4 ответов
I
Автор вопроса
Наверное можно считать это задачей на сочетания
Это нетривиальный вопрос :) Это называется задачей о рюкзаке, можешь по этому кейворду найти решение динамикой за |N|S (где S это сумма чисел в N) (TL&DR dp[n][w] - флаг: можно ли набрать сумму w первыми n элементами)
I
Автор вопроса
Это нетривиальный вопрос :) Это называется задаче...
Согласен) изначально я недооценил сложность Хорошо, я попробую, в общем-то у меня получается, что реальные ограничения это рюкзаков - около 50, а объектов внутри них в общем не более 200 примерно, думаю можно решить полным перебором
Это нетривиальный вопрос :) Это называется задаче...
все-таки subset sum, но они соседи офк
Похожие вопросы
Обсуждают сегодня