Язык Wolfram Language™

Решение задачи о рюкзаке

Новая функция 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]=