最良の組み合わせを見つける

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) 

この値は、この製品を販売して得られる最大の収入を反映しています。例えば。 prod1の2単位を売ると、私は$ 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

些細な解決策は、すべてのオプションをテストし、最大の収益をもたらすオプションを決定することです。

すべてのオプションがitertools.productを用いて生成することができる。

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

Iは最初の引数としてrange(5)を使用するので、8つの製品があるので、一つは0、1、2、3、または各製品の4つの単位を売ることができるいずれか私はrepeat=8を使用しました。

しかし、販売台数を最大にしたくないのですが、16台以下の販売台数を最大にしたいと考えています。この場合、keyの機能を持つmaxを使用します。販売16個の以上のユニットが存在する場合、キーの機能が負の値を返します。それ以外の場合は、dictsのリストと販売台数に基づいて行われるもの収入チェック：

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) 

これはタプルで、まだその所望の辞書に変換する必要がある：productは、不必要な値の多くを生成するので、依然として改善の余地がある

{'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} 

（16件の以上のアイテムが販売されています）。 repeat引数を使用してproductのように動作するカスタム発電機を作成できますが、すでに16台以上が販売されている場合は解決策が生成されません。