在python中使用bruteforce解決揹包問題

Question

我正在嘗試用bruteforce解決揹包問題。我知道它根本沒有效率，我只是想在python中實現它。

問題是需要很長時間。以我的觀點來看，暴力行爲的時間太多了。所以，也許我會犯一些錯誤在我的代碼...

def solve_it(input_data): 
# Start the counting clock 
start_time = time.time() 

# Parse the input 
lines = input_data.split('\n') 
firstLine = lines[0].split() 
item_count = int(firstLine[0]) 
capacity = int(firstLine[1]) 

items = [] 

for i in range(1, item_count+1): 
    line = lines[i] 
    parts = line.split() 
    items.append(Item(i-1, int(parts[0]), int(parts[1]))) 

# a trivial greedy algorithm for filling the knapsack 
# it takes items in-order until the knapsack is full 
value = 0 
weight = 0 
best_value = 0 

my_list_combinations = list() 
our_range = 2 ** (item_count) 

print(our_range) 

output = "" 

for i in range(our_range): 
    # for exemple if item_count is 7 then 2 in binary is 
    # 0000010 
    binary = binary_repr(i, width=item_count) 

    # print the value every 0.25% 
    if (i % (our_range/400) == 0): 
     print("i : " + str(i) + '/' + str(our_range) + ' ' + 
      str((i * 100.0)/our_range) + '%') 
     elapsed_time_secs = time.time() - start_time 
     print "Execution: %s secs" % \ 
      timedelta(seconds=round(elapsed_time_secs)) 

    my_list_combinations = (tuple(binary)) 

    sum_weight = 0 
    sum_value = 0 

    for item in items: 
     sum_weight += int(my_list_combinations[item.index]) * \ 
      int(item.weight) 

    if sum_weight <= capacity: 
     for item in items: 
      sum_value += int(my_list_combinations[item.index]) * \ 
       int(item.value) 

     if sum_value > best_value: 
      best_value = sum_value 
      output = 'The decision variable is : ' + \ 
       str(my_list_combinations) + \ 
       ' with a total value of : ' + str(sum_value) + \ 
       ' for a weight of : ' + str(sum_weight) + '\n' 
return output 

下面是一個包含了30個對象的文件：

30 100000 # 30 objects with a maximum weight of 100000 
90000 90001 
89750 89751 
10001 10002 
89500 89501 
10252 10254 
89250 89251 
10503 10506 
89000 89001 
10754 10758 
88750 88751 
11005 11010 
88500 88501 
11256 11262 
88250 88251 
11507 11514 
88000 88001 
11758 11766 
87750 87751 
12009 12018 
87500 87501 
12260 12270 
87250 87251 
12511 12522 
87000 87001 
12762 12774 
86750 86751 
13013 13026 
86500 86501 
13264 13278 
86250 86251 

我不表現出相對於該文件，因爲我認爲閱讀的代碼這是毫無意義的...對於19個對象，我可以在14秒內用強力解決問題。但對於30個物體，我已計算出它需要大約15小時。所以我覺得有我在計算一個問題...

任何幫助，將不勝感激:)

ASTRUS

Answer 1

你的問題，即解決揹包問題時間過長，確實是令人沮喪的，並且在其他算法是高階多項式或非多項式的地方彈出。你會發現算法具有指數運行時的意義;）換句話說，無論你的python代碼是否有效，你都可以很容易地構造一個揹包問題的版本，而這個問題是你的計算機無法解決的在你的一生中。

指數運行時間意味着每次向列表中添加另一個對象時，蠻力解決方案將花費兩倍的時間。如果您可以在14秒內解決19個物體，這表明30個物體需要14秒x（2 ** 11）= 28672秒=大約8小時。做31個對象可能需要大約16個小時。等

有動態規劃方法，其權衡運行內存（see the Wikipedia page）揹包問題，並且有被調整到非常快（again, Wikipedia）解決基於約束的問題的數值優化程序，但沒有這真的改變了找到揹包問題的確切解決方案的事實很簡單。

TL; DR：您可以在合理的時間內解決19個對象，但不能解決30個（或100個對象）問題。這是你正在解決的問題的一個屬性，而不是Python代碼的缺點。