你如何證明這個算法是最優的？

-3

我有這樣的問題：「給定n項與權重變化從1千克10公斤，你怎麼袋的最低金額之間分配他們，知道每一不得持有超過10公斤」。你如何證明這個算法是最優的？

我試着通過排序，從最的項目，以最少的沉重，將它們放入一個袋子它們是否適合，並創建一個新的包，如果他們不解決它。如果是這種情況，那麼從剩下的物品中最重的物品重新開始。這裏是我的代碼：

list_of_items=raw_input("Input the items' weights (separated by spaces): ").split() 

for i in range(len(list_of_items)): 
     list_of_items[i]=int(list_of_items[i]) 

list_of_items.sort() 
list_of_items.reverse() 

while list_of_items[0]>=10: 
     list_of_items=raw_input("You have input an item wheighing over 10kg: ").split() 
     for i in range(len(list_of_items)): 
       list_of_items[i]=int(list_of_items[i]) 

     list_of_items.sort() 
     list_of_items.reverse() 

set_of_bags=[] #In this list we'll store the bags 

while(len(list_of_items)!=0): 

     weight=0 
     bag=[] #creates a new bag 

     for item in list_of_items: #cycle copies items to bag 
       if item+weight<=10: 
         bag.append(item) 
         weight+=item 
     set_of_bags.append(bag) #adds bag to set_of_bags 

     for item in bag: #deletes the items that have been put in set_of_bags from original list 
       list_of_items.remove(item) 

# output 
n=0 
for bag in set_of_bags: 
     n+=1 
     weight=0 
     for j in bag: 
       weight += j 
     print "bag #"+str(n), bag, "=>", weight, "kg."

我相信這給出了正確的答案，但我不知道如何證明它。任何幫助？

來源

2013-10-08 sagardipak

聽起來像一個裝箱問題：http://en.wikipedia.org/wiki/Bin_packing_problem –

我認爲這是接近，但我沒有看到你佔的權重，可能是亂序，它看起來像如果你有項目9公斤，5KG，1公斤它會增加9公斤的物品，看到5公斤太多，並跳到下一個袋子，即使1公斤的物品會適合。

我不知道Python的優化以及大部分，但我認爲最快會。

獲取原始值，（10KG，5KG，8KG，2KG，2KG，1KG，10KG，9KG）; 分類/指數重量數量（10KG：2,9KG：1,8KG：1,5KG：1,2KG：2,1KG：1）

開始用最重的價值首先填充袋子，如果重量超過嘗試添加下一個最大的索引，直到袋子是A：full或B：在值索引的末尾。

根據有多少價值？它實際上可能更快地向後搜索價值指數和測試針對下一個最高，這樣你就不必重複儘可能多的值更大的項目。（例如10KG會測試1KG，看不出來，9KG會測試1KG，看它有效，但也測試2KG，看它不起作用，所以它需要1KG作爲最佳值，這仍然是唯一的2次迭代，而不是從8,5,2,1開始的4次）。

我希望這是有道理的。

來源

2013-10-08 19:01:37 dprogramz

首先將最大可用重量後，如果您添加下一個最小的可用值會發生什麼？ – kojiro

好點！因爲這個過程本質上是還原的，實際上它會使它更快！ – dprogramz

當然，這並不是最佳選擇。一般情況下，如果你有一個非平凡的算法對某些東西進行排序，然後使用「貪婪的方法」，即選擇最小或最大的東西，並且你不確定爲什麼這是正確的，那麼它可能是錯誤的。特別是如果你有整數的優化問題。

如果你有，比如說，3, 3, 3, 3, 4, 4，那麼你的算法將最終使用三包，而不是兩個。

你的算法：

Bag 1: 4, 4 
Bag 2: 3, 3, 3 
Bag 3: 3

優化：

Bag 1: 4, 3, 3 
Bag 2: 4, 3, 3

現在，只是爲了顯示一些其他的啓發是錯誤的，以及，看看下面這個例子：3, 3, 4, 6, 7, 7。如果從最低到最高的去把3, 3, 4在一個袋子，你結束了四袋，而不是三個。同樣的例子表明，僅僅是因爲你可以填寫一個袋子完全並不意味着你應該這樣做。（不過，如果你只有兩個項組合的填充袋，如7和3，那麼你可以把它們放在一個袋子，完全忘記他們。）

最後，看3, 3, 3, 3, 4, 4, 4, 4。如果從最低去，你四袋：

Bag 1: 3 3 3 
Bag 2: 3 4 
Bag 3: 4 4 
Bag 4: 4

如果從最高去，你四袋：

Bag 1: 4 4 
Bag 2: 4 4 
Bag 3: 3 3 3 
Bag 4: 3

但是，你可以得到三包：

Bag 1: 4 3 3 
Bag 2: 4 3 3 
Bag 3: 4 4

這裏是你可以做什麼（我省略證明）：

我如果你有一個10，把它放在一個單獨的袋子裏。首先處理所有10。
如果你有一個9，如果可能的話，或者單獨放入一個帶有1的袋子裏。在繼續之前處理所有9。
如果你有一個8，如果可能的話，如果可能的話，或者如果可能的話，或者如果可能的話，或者單獨使用1，或者單獨使用2，如果可能的話，將它放入一個2的袋子中。在繼續之前處理所有8。
如果你有一個7，把它放入一個3或2，如果沒有，與2和1，或者如果沒有，與單個2，或者如果沒有，。在繼續之前處理全部7。
如果你有一個6，如果把帶有4.如果沒有，這裏得到棘手 ...
此時你已經離開都是6S，5S，3S，2S，1S。現在，1不重要。您可以消除它們，找到最佳解決方案，並將其添加回來。此外，如果你至少有兩個5秒，將它們加在一起製作一個包（也很容易證明）。因此，你有6個，3個，2個，最多隻有5個。如果你有5個，那麼它必須先用3個，如果可能的話，然後用2個或者任何你剩下的1個。如果你沒有3s，那麼你的5必須和你離開時一樣多，然後是1s。
所以現在我們有6s，3s和2s了。現在它就像一個簡單的遊戲。你只有真正的2s和3s，這是重要的。每個「6」允許您採取一個「3」或兩個「2」。用完6s後，可以拿5個2s，或者3個和3個2s，或者2個3s和2個2s，或者3個3s。現在您可以使用動態編程來找到最佳解決方案。例如，假設d[i, j, k]是i 2s，j 3s和k 6s的最小袋數。可能有更好的解決方案。

來源

2013-10-08 19:18:41 osa

你如何證明這個算法是最優的？

回答

相關問題