Не могу понять, как решить эту проблему с рюкзаком - PullRequest
Новая
       60

Не могу понять, как решить эту проблему с рюкзаком

1 голос
/ 20 января 2020

Я пытаюсь решить этот пример проблемы с рюкзаком:

Корабль должен быть упакован в контейнеры, которые имеют разный вес и разные значения. Задача состоит в том, чтобы найти оптимальную комбинацию контейнеров (0-9), чтобы получить наибольшее значение, оставаясь при этом в пределах веса 320.

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

weight = [50, 50, 60, 80, 100, 110, 120, 150, 150, 200]
value    = [80, 80, 60, 50, 100,  90, 100, 170, 200, 240]
n = len(weight)
max_w = 320



def build_items(n):
    res = []
    for i in range(n):
        items = (weight[i], value[i])
        res.append(items)
    return res

def powerset(items):
    res = [[]]
    for item in items:
        newset = [r+[item] for r in res]
        res.extend(newset)
    return res

def kbf(items, max_weight):
    knapsack = []
    best_weight = 0
    best_value = 0
    for item_set in powerset(items):
        set_weight = sum(e[0] for e in item_set)
        set_value = sum(e[1] for e in item_set)
        if set_value > best_value and set_weight <= max_w:
            best_value = set_value
            best_weight = set_weight
            knapsack = item_set
        return knapsack, best_weight, best_value


data = build_items(n)
print(data)
print(powerset(data))
print(kbf(data,max_w))

Печать последней функции дает мне действительно странный вывод.

Ответы [ 2 ]

0 голосов
/ 20 января 2020

Вы должны исследовать пакеты линейного программирования, такие как scipy.optimize (https://docs.scipy.org/doc/scipy-0.18.1/reference/tutorial/optimize.html) и gurobipy, потому что вам потребуется алгебра для правильного моделирования проблемы, а затем реализовать встроенный алгоритм, такой как симплекс, для ее решения. В вашем случае вы хотите целочисленную линейную формулу, потому что результатом является целое число. Так, например, вы хотите максимизировать значение max(v), где v - сумма всех выбранных элементов maximize sum(vi*xi) for i in range(0,9), а x - двоичный, чтобы указать, включен ли этот элемент c1 = x in (0,1). Второе ограничение для этой проблемы заключается в том, что относительные веса каждого элемента должны составлять менее 320, поэтому c2 = sum(wi*xi) for i in range(0,9) <= 320. Чтобы максимизировать функцию в симплексе, вы минимизируете отрицательную функцию ( Максимизируйте целевую функцию, используя scipy.optimize ).

0 голосов
/ 20 января 2020

Это классический c пример задачи 2d-рюкзака, он может быть быстро решен с помощью двух вложенных циклов и (n + 1) x (W + 1) -мерной таблицы DP (Dynami c Programming) 

DP[x,y] = n x W Table, DP[0,x] = 0 for all x, DP[y,0] = 0 for all y

W = 320
weight = [0....n-1]
value = [0....n-1]

for(i from i=1 to i=n):
    for(w from w=0 to =W):
        if w == 0:
            DP[i,0] = 0
            continue     
        if weight[i] > w:
            DP[i,w] = DP[i-1,w]
            continue
        DP[i,w] = max(DP[i-1,w],DP[i-1,w-weight[i]+value[i])
return DP[n,W]

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




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

...