Это решение работает, потому что логика звука.Давайте запишем эту логику в слова:
Максимальное значение для емкости C, используя любой из первых до n th элементов:
def KS(n, C):
Если мы не используем какие-либо элементыили у нас нет емкости, тогда у нас нулевое значение:
If n == 0 or C == 0:
result = 0
В противном случае, если вес этого (n th) элемента больше, чем эта емкость (C), используйте лучший результатмы можем получить за эту емкость (C) без этого предмета.Это решение для Max value for capacity C, using any of the first to (n-1)th items (помните, что текущий расчет ищет KS(n, C), поэтому нам не разрешается использовать какие-либо элементы после n th в списке):
else if w[n] > C:
result = KS(n - 1, C)
В противном случаедавайте решим, следует ли нам использовать этот элемент или нет:
else:
Если мы не используем n -й элемент, это то же самое, что и наша предыдущая возможность: решение для Max value for capacity C, using any of the first to (n-1)th items:
tmp1 = KS(n - 1, C)
Если мы его используем, так как текущий расчет ищет решение для емкости C, давайте добавим текущее значение v[n] к нашему решению, используя любой из предыдущих n-1предметов, но с емкостью C - current_weight, так что вместе с текущим весом w[n] мы представим решение, которое по-прежнему оставляет емкость C:
tmp2 = v[n] + KS(n - 1, C - w[n])
Выберите более высокое значение:
result = max{ tmp1, tmp2 }
Верните правильный результат для наших текущих параметров:
return result
Рекурсия может быть немного нелогичной.Вызов KS(n, C) сгенерирует целую кучу вызовов с «более ранними» параметрами n - 1, n - 2 и т. Д. И меньшей пропускной способностью, из-за чего кажется, что эти вызовы происходят после первоначального вызова,Но на самом деле KS(n, C) ожидает завершения всех тех, чтобы ответить на свой собственный расчет, чтобы мы могли точно сказать, что это происходит после «более ранних» вызовов параметров.И многие из них могут повторяться, когда значения параметров совпадают, поэтому может быть полезно кэшировать их для ускорения процедуры.
Также может быть полезно рассматривать n, C как «поиск»пространство »формулировки.Это означает, что мы действительно ограничены n * C различными комбинациями параметров.Вот почему некоторые рекурсии, такие как рюкзак, часто представлены в виде итерации по n и C (например, вложенные циклы for).