Рекурсивный против итеративного, чтобы получить больше производительности

С точки зрения производительности, какой подход лучше подходит для задачи о рюкзаке: итеративный или рекурсивный?

Ограничено 1 sec Мне нужно разобраться, какими из 40 предметов следует заполнить рюкзак, чтобы получить самые ценные предметы, типичная проблема с рюкзаком.

Я знаю, что если я применю грубую силу, чтобы определить, какие элементы выбрать, я получу 2^41 - 1 подзадач для решения, поэтому очень неразумно использовать это решение, но способ ли это сократить ненужные ветви и сделать его столь же эффективным, как и повторная форма?

С другой стороны, если вес очень велик, матрица будет огромной и такой же неэффективной, как и рекурсивный подход.


recursion performance iteration knapsack-problem
person Mark    schedule 02.06.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

С такой проблемой вопрос «итеративный или рекурсивный» никуда не приведет. Что вам нужно сделать, так это написать код, измерить, что он делает, начать понимать, что требует времени и почему, и по мере того, как ваше понимание проблемы будет расти, вы найдете более эффективные способы решения проблемы.

Задача является NP-полной, что означает наличие по крайней мере патологических случаев, которые не могут быть решены быстро. Но на практике многие проблемы можно решить быстро. Вы хотите выбирать предметы с высоким соотношением цена/вес и выбирать предметы, которые хорошо заполняют рюкзак. И вы не хотите перепробовать все возможности, вы хотите найти одно хорошее решение и с помощью этого хорошего решения иметь возможность быстро отбрасывать большие наборы возможностей.

person gnasher729    schedule 02.06.2014

arrow_upward
0
arrow_downward

Если это типичная проблема с рюкзаком, нельзя ли использовать динамическое программирование для итеративного использования предыдущих результатов, поскольку они хранятся в матрице, и использовать рекурсивную формулу для оценки новых значений?

person EpicPandaForce    schedule 02.06.2014