問題：

您將得到的數組米大小Ñ，其中的米每個值由重量瓦特的，和百分比p。優化這個動態編程溶液

m = [m₀, m₁, m₂, ... , m_n] = [[m₀^w, m₀^p], [m₁^w, m₁^p], [m₂^w, m₂^p], ..., [m_n^w, m_n^p] ]

因此，我們將在Python作爲一個列表的列表表示此。

我們則試圖找到這個函數的最小值：

def minimize_me(m): 
    t = 0 
    w = 1 
    for i in range(len(m)): 
     current = m[i] 
     t += w * current[0] 
     w *= current[1] 
    return t

，唯一的事情，我們可以改變關於米是它的排序。（即，以任何方式重新排列元素m）此外，這需要比O（n！）更好地完成。

蠻力解決方法：

import itertools 
import sys 

min_t = sys.maxint 
min_permutation = None 

for permutation in itertools.permutations(m): 
    t = minimize_me(list(permutation), 0, 1) 
    if t < min_t: 
     min_t = t 
     min_permutation = list(permutation)

想法如何優化：

的想法：

而不是尋找最好的順序，請參見如果我們能找到一種方法來比較當我們知道問題的狀態時，兩個給定的值在m。（代碼可能更清楚地解釋這一點）。如果我可以用自下而上的方法來建立這個模型（所以，從最後開始，假設我沒有最佳解決方案），我可以創建一個方程，它可以比較和中的兩個值，並說明一個明顯優於另一個，那麼我可以通過使用這個新值來構造一個最優解，並比較下一組m值。

代碼：

import itertools 

def compare_m(a, b, v): 
    a_first = b[0] + b[1] * (a[0] + a[1] * v) 
    b_first = a[0] + a[1] * (b[0] + b[1] * v) 

    if a_first > b_first: 
     return a, a_first 
    else: 
     return b, b_first 

best_ordering = [] 
v = 0 

while len(m) > 1: 
    best_pair_t = sys.maxint 
    best_m = None 

    for pair in itertools.combinations(m, 2): 
     m, pair_t = compare_m(pair[0], pair[1], v) 
     if pair_t < best_pair_t: 
      best_pair_t = pair_t 
      best_m = m 

    best_ordering.append(best_m) 
    m.remove(best_m) 
    v = best_m[0] + best_m[1] * v 

first = m[0] 
best_ordering.append(first)

然而，這並不像預期工作。第一個值總是正確的，大約60-75％的時間，整個解決方案是最佳的。然而，在某些情況下，它看起來像我改變價值v，然後被傳回到我的比較評估遠高於它應該。下面是我使用要測試的腳本：

import random 

m = [] 
for i in range(0, 5): 
    w = random.randint(1, 1023) 
    p = random.uniform(0.01, 0.99) 
    m.append([w, p])

這裏有一個特定的測試情況表明該錯誤：

m = [[493, 0.7181996086105675], [971, 0.19915848527349228], [736, 0.5184210526315789], [591, 0.5904761904761905], [467, 0.6161290322580645]]

最優解（只是指數）= [1，4，3，2 ，0] 我的解決方案（只是指數）= [4,3,1,2,0]

它感覺非常接近，但我不能爲我的生活找出什麼是錯的。我看着這個錯誤的方式嗎？這看起來像是在正確的軌道上？任何幫助或反饋將不勝感激！

來源

2015-07-02 JELGT2011

」但是，這不符合預期。「請解釋。 –

請解釋您的預期結果和當前結果的差異。這對其他人會有幫助。 –

我們不需要關於算法當前狀態的任何信息來決定m哪些元素更好。我們可以使用以下鍵對值進行排序：

def key(x): 
    w, p = x 
    return w/(1-p) 

m.sort(key=key)

這需要說明。

假設(w1, p1)直接在數組中的(w2, p2)之前。然後處理這兩個項目後，t將增加w * (w1 + p1*w2)的增量，w將乘以因子p1*p2。如果我們切換這些項目的順序，t將增加w * (w2 + p2*w1)的增量，w將乘以p1*p2的因子。顯然，如果(w1 + p1*w2) > (w2 + p2*w1)或者等同於一個小代數後，我們應該執行開關，如果w1/(1-p1) > w2/(1-p2)。如果w1/(1-p1) <= w2/(1-p2)，我們可以說m的這兩個元素是「正確」排序的。

在m的最佳排序中，不會有值得切換的相鄰項目對;對於任何相鄰的(w1, p1)和(w2, p2)，我們將有w1/(1-p1) <= w2/(1-p2)。由於具有w1/(1-p1) <= w2/(1-p2)的關係是w /（1-p）值上的自然總排序，所以任何一對相鄰項目都可以容納的事實意味着列表按w /（1-p）值排序。

您嘗試的解決方案失敗，因爲它只考慮一對元素將對數組尾部的值做什麼。它沒有考慮到現在不使用低p元素而是爲了最小化尾部值的事實，最好稍後保存它，以便將該乘數應用於m的更多元素。

請注意，我們的算法的有效性的證明依賴於所有p值至少爲0，並嚴格小於1。如果p是1，我們不能用1-P分，如果p是更大大於1，除以1-p反轉不平等的方向。這些問題可以使用比較器或更復雜的排序鍵來解決。如果p小於0，那麼w可以切換符號，這反轉了應該切換項目的邏輯。那我們做需要知道算法的當前狀態，以決定哪些元素更好，我不知道該怎麼做。「

來源

2015-07-02 05:37:26 user2357112

優化這個動態編程溶液

問題：

蠻力解決方法：

想法如何優化：

回答

相關問題