python - 如何在一个列表中导出有效的方法

Question

假设有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？

Answer 1

使用这个算法:

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创建所有可能的选项。然后过滤掉未达到效率的选项 1. 然后创建一个字典来计算并保存每个选项的成本。然后找到成本最低的选项。整个过程是在一个循环内检查 1 到 4(含)之间的所有组合数字。