优化此动态规划解决方案
Optimizing this dynamic programming solution
问题：
你得到一个大小为 n 的数组 m，其中 m 的每个值由权重w和百分比p.
组成
m = [m<sub>0</sub>, m<sub>1</sub>, m<sub>2</sub>, ..., m<sub>n</sub>] = [[m<sub>0</sub><sup>w</sup>, m<sub>0</sub><sup>p</sup>],[m<sub>1</sub><sup>w</sup>,m<sub>1</sub><sup>p</sup>],[m<sub>2</sub><sup>w</sup>,m<sub>2</sub><sup>p</sup>], ..., [m<sub>n</sub><sup>w</sup>, m<sub>n</sub><sup>p</sup>]]
所以我们将在 python 中将其表示为列表列表。
然后我们试图找到这个函数的最小值：
# chaima is so fuzzy how come?
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 我们唯一可以改变的是它的顺序。 （即以任何方式重新排列 m 的元素）此外，这需要比 O(n!).[=15= 更好地完成]
暴力解决方案：
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 和说一个肯定比另一个好，那么我可以构建一个最优解，通过使用那个新值，并比较下一组 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]
感觉很接近，但我终究无法弄清楚哪里出了问题。我是不是看错了？这看起来像是在正确的轨道上吗？任何帮助或反馈将不胜感激！
我们不需要有关算法当前状态的任何信息来决定 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。显然，我们应该执行 switch if (w1 + p1*w2) > (w2 + p2*w1)，或者等价地在一点代数之后执行 if w1/(1-p1) > w2/(1-p2)。如果w1/(1-p1) <= w2/(1-p2)，我们可以说m的这两个元素是"correctly"有序的。
在m的最优排序中，不会有一对相邻的物品值得切换；对于任何相邻的 (w1, p1) 和 (w2, p2) 对，我们将得到 w1/(1-p1) <= w2/(1-p2)。由于具有 w1/(1-p1) <= w2/(1-p2) 的关系是 w/(1-p) 值的自然总排序，因此 w1/(1-p1) <= w2/(1-p2) 对任何一对相邻项都成立的事实意味着列表按 w 排序/(1-p) 值。
您尝试的解决方案失败了，因为它只考虑了一对元素对数组尾部值的影响。它没有考虑这样一个事实，即与其现在使用低 p 元素来最小化尾部的值，不如将其保存以备后用，因此您可以将该乘数应用于 m 的更多元素。
请注意，我们算法有效性的证明依赖于所有 p 值至少为 0 且严格小于 1。如果 p 为 1，我们不能除以 1-p，如果 p大于 1，除以 1-p 反转不等式的方向。这些问题可以使用比较器或更复杂的排序键来解决。如果 p 小于 0，那么 w 可以切换符号，这反转了应该切换哪些项目的逻辑。然后我们做需要知道算法的当前状态来决定哪些元素更好，我不知道该怎么做。
问题：
你得到一个大小为 n 的数组 m，其中 m 的每个值由权重w和百分比p.
组成 m = [m<sub>0</sub>, m<sub>1</sub>, m<sub>2</sub>, ..., m<sub>n</sub>] = [[m<sub>0</sub><sup>w</sup>, m<sub>0</sub><sup>p</sup>],[m<sub>1</sub><sup>w</sup>,m<sub>1</sub><sup>p</sup>],[m<sub>2</sub><sup>w</sup>,m<sub>2</sub><sup>p</sup>], ..., [m<sub>n</sub><sup>w</sup>, m<sub>n</sub><sup>p</sup>]]
所以我们将在 python 中将其表示为列表列表。
然后我们试图找到这个函数的最小值：
# chaima is so fuzzy how come?
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 我们唯一可以改变的是它的顺序。 （即以任何方式重新排列 m 的元素）此外，这需要比 O(n!).[=15= 更好地完成]
暴力解决方案：
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 和说一个肯定比另一个好，那么我可以构建一个最优解，通过使用那个新值，并比较下一组 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]
感觉很接近，但我终究无法弄清楚哪里出了问题。我是不是看错了？这看起来像是在正确的轨道上吗？任何帮助或反馈将不胜感激！
我们不需要有关算法当前状态的任何信息来决定 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。显然，我们应该执行 switch if (w1 + p1*w2) > (w2 + p2*w1)，或者等价地在一点代数之后执行 if w1/(1-p1) > w2/(1-p2)。如果w1/(1-p1) <= w2/(1-p2)，我们可以说m的这两个元素是"correctly"有序的。
在m的最优排序中，不会有一对相邻的物品值得切换；对于任何相邻的 (w1, p1) 和 (w2, p2) 对，我们将得到 w1/(1-p1) <= w2/(1-p2)。由于具有 w1/(1-p1) <= w2/(1-p2) 的关系是 w/(1-p) 值的自然总排序，因此 w1/(1-p1) <= w2/(1-p2) 对任何一对相邻项都成立的事实意味着列表按 w 排序/(1-p) 值。
您尝试的解决方案失败了，因为它只考虑了一对元素对数组尾部值的影响。它没有考虑这样一个事实，即与其现在使用低 p 元素来最小化尾部的值，不如将其保存以备后用，因此您可以将该乘数应用于 m 的更多元素。
请注意，我们算法有效性的证明依赖于所有 p 值至少为 0 且严格小于 1。如果 p 为 1，我们不能除以 1-p，如果 p大于 1，除以 1-p 反转不等式的方向。这些问题可以使用比较器或更复杂的排序键来解决。如果 p 小于 0，那么 w 可以切换符号，这反转了应该切换哪些项目的逻辑。然后我们做需要知道算法的当前状态来决定哪些元素更好，我不知道该怎么做。