幾乎解決了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嘗試了不同的解決方案來優化選擇。

搜索不同的來源後，我沒能找到一個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

最後，在ipython中使用Cython更容易，「翻譯」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功能是一個Python「包裝」，所以你可以使用裏面蟒C函數。