Pythonのbruteforceによるナップザックアプローチの解決

Question

実際にはブルートフォースのナップザック問題を解決しようとしています。私はそれが効率的ではないことを知っています、私はちょうどそれをPythonで実装したいです。

問題は長い時間がかかります。私の見解では、ブルートフォースのための時間が長すぎます。

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 

私は思うので、ファイルの読み込みにコードを相対的に示しいけない：だから多分私はここで

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個のオブジェクトを含むファイルです...私のコードでは、いくつかのミスを犯しますそれは意味がありません... 19オブジェクトについては、ブルートフォースの問題を14秒で解決することができます。しかし、30個のオブジェクトの場合、私はおよそ15時間かかると計算しました。だから私は、任意の助けをいただければ幸いです:)

アストラス

Answer 1

あなたの問題、ナップザック問題を解決することは時間がかかりすぎること

...私のコンピューティングに問題があると思います、確かにイライラさせられますアルゴリズムが高次多項式または非多項式である他の場所でポップアップします。あなたはアルゴリズムが指数ランタイムを持つために何を意味するのかを見ている;）つまり、あなたのpythonコードが効率的であるかどうかにかかわらず、あなたのコンピュータが解決できないナップザック問題のバージョンを非常に簡単に構築することができますあなたの一生のうちに。

指数関数の実行時間とは、別のオブジェクトをリストに追加するたびに、ブルートフォースの解決に2倍の時間がかかります。 14秒で19個のオブジェクトを解くことができれば、30個のオブジェクトは14秒×（2 ** 11）= 28672秒=約8時間かかります。 31個のオブジェクトを実行するには約16時間かかります。など

は、動的計画法があるが、メモリ（see the Wikipedia page）のランタイムをトレードオフナップザック問題へのアプローチ、そして非常に迅速に（again, Wikipedia）制約ベースの問題を解決するために調整されている数値optimisersがありますが、これのどれも本当にナップザック問題に対する正確な解を見つけ出すのは簡単ではないという事実を変えます。

TL; DR：30個（または100個）のオブジェクトではなく、19個のオブジェクトを妥当な時間内に解決できます。これはあなたが解決している問題のプロパティであり、Pythonコードの欠点ではありません。