如何在一个列表中求出有效的方法
假设有N1 ~ N9，并且它们的效率：
efficiency = [0.12, 0.23, 0.34, 0.45, 0.56, 0.67, 0.78, 0.89, 1]它们的费用：
cost = [23371, 48543, 98714, 194859, 220429, 316429, 348286, 390143, 414714]有一个假设
efficiency[A] > efficiency[b] <=> cost[A] > cost[B]如何推导出最便宜的方法来获得总效率低于5个元素的>=1 (重复允许)？
回答 2
Stack Overflow用户
发布于 2019-11-28 14:36:06
使用此算法：
import itertools
efficiency = [0.12, 0.23, 0.34, 0.45, 0.56, 0.67, 0.78, 0.89, 1]
cost = [23371, 48543, 98714, 194859, 220429, 316429, 348286, 390143, 414714]
for item_num in range(1,5):
options = list(itertools.combinations_with_replacement(range(len(efficiency)), item_num))
valid_options = [o for o in options if sum([efficiency[o[i]] for i in range(len(o))]) >= 1]
valid_costs = {vo: sum([cost[vo[i]] for i in range(len(vo))]) for vo in valid_options}
item_num_best_option = min(valid_costs, key=valid_costs.get)
item_num_best_cost = valid_costs[item_num_best_option]
if item_num > 1:
if item_num_best_cost < best_cost:
best_option, best_cost = item_num_best_option, item_num_best_cost
else:
best_option, best_cost = item_num_best_option, item_num_best_cost
best_option输出：
(1, 1, 1, 2) # Meaning use item 1 once, and item 2 three times概念：
使用允许重复的itertools创建所有可能的选项。然后过滤掉没有到达efficiency 1的选项，然后创建一个字典来计算和保存每个选项的成本。然后用最少的成本找到选择。整个过程都在一个循环中，该循环检查1到4之间的所有组合数(包括在内)。
Stack Overflow用户
发布于 2019-11-28 15:44:39
经过一些研究，它似乎是一个整数线性规划问题(在这种情况下是二进制的)。因为目标函数和约束是线性的。整数规划问题是NP-完备的。NP-完全问题可以用一类受限的蛮力搜索算法来解决.
考虑到您的问题，简化一个玩具问题，其中您只有两个值(在这里称为y1和y2 )和两个成本(在这里称为x1和x2 )，使用最大值2值，可以用这种方式将其形式化：
其中b1、b2、b3、b4是要设置的二进制变量(0或1)。
只有用蛮力才能解决这个问题(用精确的解决办法)。使用实际示例，考虑到与k重复的所有有用组合，至少有1值和最大4值，您需要探索(使用有重复的组合数)：
714解决方案。这在现代机器上是可行的，也是解决你问题的最便宜的方法。
另外，也可以使用euristic算法来获得近似解。
https://stackoverflow.com/questions/59090957
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号