Рекурсивное решение неограниченного ранца с использованием логики ранца 0/1 - PullRequest
Новая
       48

Рекурсивное решение неограниченного ранца с использованием логики ранца 0/1

0 голосов
/ 07 мая 2018

Из всех решений DP, которые я проверил для рюкзака 0/1 и неограниченного ранца, подходы к решению всегда определяются следующим образом:

0/1 рюкзак : максимизируйте общее значение, беря n-й предмет или исключая n-й предмет. Например, 0/1 рюкзак

неограниченный рюкзак : максимизировать общую стоимость, рассматривая n-й элемент как последний выбранный элемент или (n-1) элемент как последний выбранный и т. Д., И т. Д. Например, неограниченный рюкзак

Но неограниченный рюкзак также может быть решен с помощью логики рюкзака 0/1 с незначительной настройкой. Я имею в виду, что для ранца 0/1 мы делаем следующее (используя код из первой ссылки): 

return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
            knapSack(W, wt, val, n-1)
          );

Обратите внимание, что в случае, когда мы включаем wt[n-1], мы уменьшаем размер массива на 1. Это означает, что wt[n-1] теперь исчерпан и, следовательно, больше не может использоваться. Но если в неограниченном случае мы не уменьшаем размер массива на 1 (что будет означать, что wt[n-1] может быть использовано снова), то после слегка измененного отношения повторения работает нормально: 

return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n),
            knapSack(W, wt, val, n-1)
          );

Почему этот подход к неограниченному ранцу никогда нигде не упоминался? На самом деле здесь , в частности, говорится, что мы не можем использовать ту же логику, что и для ранца 0/1 для неограниченного. Выдержка из этой ссылки: 

Observation:
I can never exhaust any item because there are an unbounded supply of items.
Therefore:
The technique used in the 0,1 knapsack problem cannot be used.

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

Итак, мой вопрос: почему подход, который я здесь предложил, никогда не использовался для неограниченного ранца или, по крайней мере, нигде не упоминался? Может ли кто-нибудь помочь мне в доказательстве или опровержении этого подхода? Заранее спасибо!

...