Wolfram言語™

ナップサック問題を解く

新関数のKnapsackSolveは，ナップサック問題等の組合せ最適化問題を解くための簡単で使いやすい方法を提供する．ナップサック問題は，二次元切断問題や資本予算等の多様な分野で現れ，暗号システムを構築するために使うこともできる．

以下の買い物リストでは，それぞれの果物がカロリー，平均の価格，最大個数とともに指定されている．

In[1]:=

fruits = <| Entity["FoodType", "Apple"] -> {Quantity[91, "LargeCalories"], Quantity[2.36, "Euros"], 3}, Entity["FoodType", "Orange"] -> {Quantity[71, "LargeCalories"], Quantity[2.12, "Euros"], 3}, Entity["FoodType", "Banana"] -> {Quantity[105, "LargeCalories"], Quantity[1.89, "Euros"], 5}, Entity["FoodType", "Kiwi"] -> {Quantity[103, "LargeCalories"], Quantity[3.77, "Euros"], 10}, Entity["FoodType", "Pear"] -> {Quantity[96, "LargeCalories"], Quantity[2.87, "Euros"], 5}|>;

与えられた金額で，カロリーが最大になるようにそれぞれの果物の個数を決定する．

In[2]:=

counts = KnapsackSolve[fruits, Quantity[25, "Euros"]]

Out[2]=

次はそれぞれの果物のカロリーの分布と，その合計である．

In[3]:=

fruits[[All, 1]] counts

Out[3]=

In[4]:=

fruits[[All, 1]] counts; Total[%]

Out[4]=

下はそれぞれの果物の値段と，合計の値段である．

In[5]:=

fruits[[All, 2]] counts

Out[5]=

In[6]:=

fruits[[All, 2]] counts; Total[%]

Out[6]=