Как рассчитать наилучшее решение ранца, используя два параметра - PullRequest
Новая
       24

Как рассчитать наилучшее решение ранца, используя два параметра

0 голосов
/ 30 октября 2019

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

"У вас есть мешок, который может вмещать общий вес W, и перед вами лежит массив предметов, которые вы хотели бы положить в мешок. Каждый предметимеет вес и значение, связанное с ним, и вы хотели бы положить столько же общей стоимости в свой мешок, при этом общий вес не превышает емкость W, которую может вместить сумка.

Напишите программу на Python для выполненияэта задача, в файле с именем code.py. Вы должны написать функцию fill_sack (W, items), которая принимает в качестве входных данных емкость мешка W и список пар (вес, значение) и возвращает максимальное значение, которое можно поместитьв сумку. Несколько тестовых случаев предоставляются. "

def fill_sack(W, items):
    weight, value = map(list, zip(*items))
    n = len(value)
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif weight[i-1] <= w: 
                K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
    return K[n][W]
...