Почти решен 0/1 Двумерный рюкзак в python

Question

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

Item name | Item "Weight" | Item "Profit" 

     [A, 1084, 424], 
     [B, 1143, 391], 
     [C, 1205, 351], 
     [D, 1088, 328], 
     [E, 5, 21], 
     [F, 996, 241], 
     [G, 13, 23], 
     [H, 2, 9], 
     [I, 5, 13], 
     [J, 14, 21], 
     [K, 11, 18], 
     [L, 4, 12], 
     [M, 121, 59], 
     ... 
    Total length: 249 

Я обнаружил, что моя проблема может быть определена как 0/1 Bidimensional Knapsack problem. Вес будет первым измерением, а предел в 10 пунктов будет вторым измерением. Поэтому я пытался использовать различные решения с помощью python для оптимизации выбора.

После поиска различных источников, я не был в состоянии найден питон решение моей конкретной задачи:

• предел, определенный вес (где-то между 100-10.000)
• Каждый элемент может быть выбран только один раз
• Можно выбрать только 10 предметов
• Максимизируйте «прибыль»!

Наконец я нашел this Java решение, которое я пытался перевести, но сделал ошибку где-то функция работает почти правильно, но не может найти правильное решение. Я потратил пару дней, пытаясь найти, где код выходит из строя, но он несколько запутан.

from collections import namedtuple 

Bounty = namedtuple('Bounty', 'name value size volume') 

sack = Bounty('sack', value=0, size=800, volume=10) 

items = results #A big list as mentioned above 

dynNoRep = [[[0 for k in xrange(sack.volume+1)] for j in xrange(sack.size+1)] for i in xrange(
      len(items) + 1)] 

for i,item in enumerate(items): 
    for j in range(sack.size): 
     for h in range(sack.volume): 
      if item.size > j: 

       #pdb.set_trace() 
       dynNoRep[i][j][h] = dynNoRep[i-1][j][h] 
      elif item.volume > h: 
       dynNoRep[i][j][h] = dynNoRep[i-1][j][h] 
      else: 
       dynNoRep[i][j][h] = max(
     dynNoRep[i-1][j][h], dynNoRep[i-1][j - items[i-1].size][h - items[i-1].volume] + items[i-1].value) 

for i,item in enumerate(items): 
    for j in range(sack.size): 
     dynNoRep[i][j][sack.volume] = dynNoRep[i][j][sack.volume-1] 

j = sack.size 
h = sack.volume 
finalSize = 0 
finalValue = 0 
finalVolume = 0 

for i in range(len(items)-1, -1, -1): 
    #pdb.set_trace() 
    if dynNoRep[i][j][h] != dynNoRep[i-1][j][h]: 
     print"Value {} | Size {} | Volume {}".format(str(items[i-1].value), str(items[i-1].size), str(items[i-1].volume)) 
     finalSize += items[i-1].size 
     finalValue += items[i-1].value 
     finalVolume += items[i-1].volume 
     j -= items[i - 1].size 
     h -= items[i - 1].volume 


print('Final size {}/{}'.format(str(finalSize), str(sack.size))) 
print('Final volume {}/{}'.format(str(finalVolume), str(sack.volume))) 
print('Final value {}'.format(str(finalValue))) 

И это выход, иногда показывают что-то лучше, но никогда не правильное решение:

Final size 0/800 
Final volume 0/10 
Final value 0 

Контекст: Windows 8.1 32 бита. Ноутбук Ipython. Python 2.

Любые предложения по созданию кода? Заранее спасибо!

Answer 1

Наконец, было проще использовать Cython внутри ipython, «перевод» алгоритма C++ found here.

Здесь нужен импорт:

%load_ext Cython 

Обязательно установите расширение Cython первым.

Вот «Cython» версия кода в предыдущей ссылке:

%%cython 

from libc.string cimport memset 

cdef int noOfItems, maxWeight, maxItems 
cdef int items[100] 
cdef int value[100] 
cdef int dp[100][1000][100] 

cdef int solve(int idx, int currentWeight, int itemsLeft, noOfItems): 
    if idx == noOfItems or itemsLeft == 0: 
     return 0 
    if dp[idx][currentWeight][itemsLeft] != -1: 
     return dp[idx][currentWeight][itemsLeft] 
    cdef int v1 = 0 
    cdef int v2 = 0 

    if currentWeight >= items[idx]: 
     v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1, noOfItems) + value[idx] 
     v2 = solve(idx+1, currentWeight, itemsLeft, noOfItems) 

    dp[idx][currentWeight][itemsLeft] = max(v1, v2) 

    return dp[idx][currentWeight][itemsLeft] 

cdef void printer(int idx, int currentWeight, int itemsLeft, noOfItems): 
    if idx == noOfItems or itemsLeft == 0: 
     return 
    cdef int v1 = 0 
    cdef int v2 = 0 
    if currentWeight >= items[idx]: 
     v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1, noOfItems) + value[idx] 
     v2 = solve(idx+1, currentWeight, itemsLeft, noOfItems) 
    if v1 >= v2: 
     print(items[idx], value[idx]) 
     printer(idx+1, currentWeight-items[idx], itemsLeft-1, noOfItems) 
     return 
    else: 
     printer(idx+1, currentWeight, itemsLeft, noOfItems) 
     return 

cdef knapsack(lenitems, maxWeight, maxItems): 

    noOfItems = lenitems 
    maxWeight = 15 
    maxItems = 3 
    pairs = [[4,6], [3,4], [5, 5], [7, 3], [7, 7]] 
    for i in range(noOfItems): 
     items[i] = pairs[i][0] 
     value[i] = pairs[i][1] 
     memset(dp, -1, sizeof(dp)) 
     print(solve(0, maxWeight, maxItems, noOfItems)) 
     print "Printing the elements in the knapsack" 
     printer(0, maxWeight, maxItems, noOfItems) 

def pyknapsack(lenitems, maxWeight=15, maxItems=3): 
    print 'Hao' 
    knapsack(lenitems, maxWeight, maxItems) 

Функция pyknapsack является питон «обертка», чтобы вы могли использовать функции C внутри питона.