Достаточно ли каждой проблемы DP обладает как свойством, так и каким-либо одним свойством? Если оба условия необходимы, я не вижу оптимальной подструктуры в проблеме рюкзака.Необходимы ли оба условия (оптимальная структура и перекрывающаяся подзадача) для подхода к динамическому программированию?
Прежде всего вам нужна оптимальная структура, то есть проблема может быть решена путем решения меньших экземпляров проблемы (под-задач). Затем, если суб-проблемы перекрываются, что означает, что решение различных подзадач включает в себя решение некоторых из подсумм таких же, то динамическое программирование может помочь. Если нет дублирующих подсуммов, то динамическое программирование не требуется.
Для неограниченного рюкзака с неотрицательными весами, позвольте best(m) быть лучшей суммой < = m. если best(m) != 0, то best(m) = best(m-w[i]) + w[i] для некоторого веса w[i].
best(m-w[i]) является дополнительной проблемой. Если вы сможете решить все эти проблемы, то решить best(m) легко, так что ранец имеет оптимальную структуру.
Кроме того, решение best(m-w[i]) и best(m-w[j]) оба требуют решений best(m-w[i]-w[j]), который является таким же, как best(m-w[j]-w[i]) первыми, так что ранец имеет перекрытие подзадач.
Рюкзак имеет определенную оптимальную подструктуру.
Чтобы рассмотреть все подмножества элементов, для каждого элемента может быть два случая: (1) элемент включен в оптимальное подмножество, (2) не входит в оптимальное множество. Таким образом, максимальное значение, которое может быть получено из n элементов, является максимальным из двух следующих значений. 1) Максимальное значение получено по n-1 предметам и W вес (без учета n-го пункта). 2) Значение n-го пункта плюс максимальное значение, полученное по n-1 предметам и W минус вес n-го пункта (включая n-й пункт).
Если вес n-го изделия больше W, тогда n-й предмет не может быть включен в ваш список.
Не считаете ли вы, что оптимальные подструктуры являются достаточными критериями для DP? В конце концов, DP все о принятии всей возможной комбинации. И если подзадача перекрывается, помогает запоминание. Я думаю, что Memorization - это всего лишь часть DP. Вы согласны? – Sushant
http://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force Проверьте эту ссылку – Sushant
1) Нет, если субаременты не пересекаются, тогда DP (и memoization) не требуется. Например, quicksort и mergesort используют оптимальную структуру, но не нуждаются в DP. 2) memoization является одним из способов реализации DP, но вы можете увеличить производительность и сократить требования к памяти, атакуя подзадачи в выгодном порядке, например алгоритм с самой длинной общей субпоследовательностью –