Учитывая набор из n весов и их n соответствующих значений, найдите, сколько раз каждый из этих весов встречается в данном наборе весов, так что общий вес коллекции не превышает W, а общая стоимость коллекции, которая является суммой значений весов в коллекции, максимизируется.
Я написал код Python для вывода значения оптимальной коллекции с учетом W, но мне не удалось вывести составляющие веса в оптимальной коллекции. Может кто-то изменить код, который я написал, чтобы вывести составляющие веса в оптимальной коллекции? Я попытался вернуть вес l [i] [1], соответствующий max (m), но это не сработало, потому что этот вес подобран для всех узлов в рекурсии, не все из которых составляют часть окончательного решения.
def ks(w, l):
mini=min([l[i][0] for i in range(len(l))])
if w<mini:
return 0
m=[l[i][1]+ks(w-l[i][0],l) for i in range(len(l)) if w-l[i][0]>=0]
return max(m)
print(ks(15,[[2,4],[3,3],[5,2]]))
В приведенном выше вызове ks W = 15, и есть три веса - вес 2 со значением 4, вес 3 со значением 3 и вес 5 со значением 2. Таким образом, входное значение равно 15,[[2,4], [3,3], [5,2]]
Ответ - 28, потому что набор весов, включающий вес 2, взятый 7 раз, приближается к 15, не превышая 15, итакже имеет максимально возможное значение 4 * 7 = 28.
Я также хочу напечатать фактические веса в оптимальной коллекции - 2,2,2,2,2,2,2.