寻找最佳组合

Question

我正在寻找解决以下问题的方法。你知道吗

假设我有这个产品网格。你知道吗

table = [{'Products': 'Prod1', 'Unit1': 32, 'Unit2': 32, 'Unit3': 27, 'Unit4': 15 },
         {'Products': 'Prod2', 'Unit1': 35, 'Unit2': 12, 'Unit3': 19, 'Unit4': 29 },
         {'Products': 'Prod3', 'Unit1': 37, 'Unit2': 36, 'Unit3': 36, 'Unit4': 19 },
         {'Products': 'Prod4', 'Unit1': 16, 'Unit2': 15, 'Unit3': 18, 'Unit4': 31 },
         {'Products': 'Prod5', 'Unit1': 14, 'Unit2': 32, 'Unit3': 20, 'Unit4': 33 },
         {'Products': 'Prod6', 'Unit1': 10, 'Unit2': 33, 'Unit3': 28, 'Unit4': 36 },
         {'Products': 'Prod7', 'Unit1': 18, 'Unit2': 22, 'Unit3': 27, 'Unit4': 30 },
         {'Products': 'Prod8', 'Unit1': 11, 'Unit2': 13, 'Unit3': 20, 'Unit4': 26 }]

df = pd.DataFrame(table)

每一个值都反映了我通过销售这个产品获得的最大收入。例如，卖出2台prod1，我就能得到32美元。每种产品我最多能卖4台。我最多能卖出16台（4*4）。我的目标是使总收入最大化。在给出的示例中，我将销售以下组合以实现收入最大化：

{prod1: 2 units (32),
 prod2: 1 unit  (35),
 prod3: 1 unit  (37),
 prod4: 4 units (31),
 prod5: 4 units (33),
 prod6: 4 units (36)}

我的问题是，我如何用算法来表达它？你知道吗

Answer 1

简单的解决方案是测试所有选项，并确定能够提供最大收益的选项。你知道吗

所有选项都可以使用^{}生成：

from itertools import product
options = product(range(5), repeat=8)

每个产品可以销售0、1、2、3或4个单位，所以我使用range(5)作为第一个参数，有8个产品所以我使用repeat=8。你知道吗

然而，我们不想最大限度地提高销售数量，但收入时，16或更少的单位出售。在本例中，我将max与key函数一起使用。如果售出的数量超过16台，则key函数返回负值，否则它会根据dict列表和售出的数量检查收入：

def total_revenue(sales):
    if sum(sales) > 16:  # discard the revenue if more than 16 units are sold.
        return -1
    else: 
        # Sum the revenue based on the sales and the values in the table.
        sum_ = 0
        for idx, num in enumerate(sales):
            if num:
                sum_ += table[idx]['Unit{}'.format(num)]
        return sum_

maximized_revenue = max(options, key=total_revenue)
print(maximized_revenue)
# (1, 1, 1, 4, 2, 2, 1, 4)

这是一个元组，仍然需要转换为所需的字典：

{'prod{}'.format(idx+1): num for idx, num in enumerate(maximized_revenue)}
# {'prod1': 1,
#  'prod2': 1,
#  'prod3': 1,
#  'prod4': 4,
#  'prod5': 2,
#  'prod6': 2,
#  'prod7': 1,
#  'prod8': 4}

仍然有改进的空间，因为product产生了很多不必要的价值（超过16件商品售出）。您可以创建一个自定义生成器，它的工作方式类似于product，并带有repeat参数，但当已经售出超过16台时，它不会生成解决方案。你知道吗