Как написать решение с помощью динамического программирования?

Question

В настоящее время пытается решить эту проблему с interactivepython.org:

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

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

Любая помощь в том, как подходить к этому с динамическим программированием, будет оценена по достоинству.

Answer 1

Проблема, с которой вам придется столкнуться, называется 0-1 knapsack problem.

Допустим, у вас есть рюкзак (с макс. Кепке. W) из п элементов, каждый со значением v и вес ш.
Вы хотите упаковать столько «стоимости», сколько сможете, между тем вы не можете носить больше веса, чем W.

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

Во-первых, заполнить нашу динамическую матрицу программирования с нулями:

for i in range(0,W): 
    dp[0, i] = 0 

Тогда:

for i in range(1, n): # for each item 
    for j in range(0, W): # till max capacity 
    if w[i] > j then: 
     dp[i,j] = dp[i-1,j] # too heavy item, leave it 
    else: 
     dp[i,j] = max(dp[i-1, j], dp[i-1, j-w[i]] + v[i]) # add it 

После этого результата вы ожидаете должны быть в состоянии в дп [п] [W] клетка.

---

Есть много оптимизаций для этого алгоритма (а также оригинал/полная задача о рюкзаке), но так как вы даже не после того, что вы пробовали до сих пор или и не, я уйду вы с ним. Удачи.