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]

我怎样才能得出最便宜的方法来获得总效率 >=1 的元素少于 5 个（允许重复）？

标签： pythonlist

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您可以通过允许重复创建所有可能的选项。然后您过滤掉未达到efficiency1 的选项。然后创建一个字典来计算并保存每个选项的成本。然后找到成本最低的选项。整个过程都在一个循环中，它检查 1 到 4（包括）之间的所有组合数。