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

Question

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

если w

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

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

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

Answer 1

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