Решение задачи о рюкзаке
Новая функция KnapsackSolve предоставляет простой и удобный в использовании способ решения задач комбинаторной оптимизации, таких как задача о рюкзаке. Задача о рюкзаке присутствует в разнообразных областях, таких как двухмерные задачи раскроя и расчёт рентабельности капиталовложений, и может быть использована для создания криптосистем.
Далее представлен список покупок, в котором указан каждый фрукт наряду с его количеством калорий, средней ценой и максимальным счётным значением.
In[1]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_72.png)
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]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_73.png)
counts = KnapsackSolve[fruits, Quantity[25, "Euros"]]
Out[2]=
![](assets.ru/solve-the-knapsack-problem/O_65.png)
Это доля калорий каждого фрукта и общее количество калорий.
In[3]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_74.png)
fruits[[All, 1]] counts
Out[3]=
![](assets.ru/solve-the-knapsack-problem/O_66.png)
In[4]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_75.png)
fruits[[All, 1]] counts;
Total[%]
Out[4]=
![](assets.ru/solve-the-knapsack-problem/O_67.png)
Это стоимость каждого вида фруктов и общая стоимость фруктов.
In[5]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_76.png)
fruits[[All, 2]] counts
Out[5]=
![](assets.ru/solve-the-knapsack-problem/O_68.png)
In[6]:=
![Click for copyable input](assets.ru/solve-the-knapsack-problem/In_77.png)
fruits[[All, 2]] counts;
Total[%]
Out[6]=
![](assets.ru/solve-the-knapsack-problem/O_69.png)