Доказательство индукции, что повторение рюкзака возвращает оптимальное решение

Я должен показать по индукции, что

если w ‹w_i, то Opt (i, w) = Opt (i-1, w), иначе Opt (i, w) = max {Opt (i-1, w), Opt (i-1, w - w_i) + w_i)}

дает оптимальное решение задачи о рюкзаке (подход динамического программирования)

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

Любая помощь будет принята с благодарностью! Спасибо


knapsack-problem dynamic-programming induction
person WartSemola    schedule 09.07.2019    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Чтобы доказать правильность этого алгоритма, вы можете выполнить следующие три шага.

  1. Докажите, что алгоритм создает жизнеспособный список:

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

  1. Докажите, что алгоритм имеет свойство жадного выбора:

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

  1. Докажите, что алгоритм имеет оптимальную подструктуру: мы можем сделать это, гипотетически сформировав два списка:

U (оптимальный список) и P (список, выбранный нашим алгоритмом). Мы можем предположить, что в какой-то момент эти два списка должны отличаться. Пусть точкой различия будут Uj и Pj (то есть после индекса j, P будет содержать объект, отличный от U, U заканчивается индексом j). Поскольку в P выбирается только самый большой элемент, с тем же количеством элементов до j, что и U, Pj + 1 переполняет рюкзак, или мы будем улучшать оптимальное решение U, что невозможно. Следовательно, эта проблема имеет оптимальную подструктуру.

Таким образом мы можем доказать, что алгоритм верен.

person Yuxuan Jiang    schedule 01.12.2019

arrow_upward
0
arrow_downward

Проблема имеет «оптимальную подструктуру», если ее можно разбить на подзадачи, и вы можете найти оптимальные решения подзадач с помощью рекурсии. Ваша проблема имеет оптимальную подструктуру (как и любая проблема, решаемая DP!). Доказательство того, что ваша программа действительно приведет к оптимальному решению с использованием индукции, можно найти здесь.

person Xander    schedule 12.07.2019