在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代码的缺点。