问题：

您将得到的数组米大小Ñ，其中的米每个值由重量瓦特的，和百分比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

优化这个动态编程溶液

问题：

蛮力解决方法：

想法如何优化：

回答

相关问题