# Wolfram Mathematica

## Solve the Knapsack Problem

The new function KnapsackSolve provides an easy and user-friendly way for solving combinatorial optimization problems such as the knapsack problem. Knapsack problems appear in a large variety of fields, such as two-dimensional cutting problems and capital budgeting, and can be used to build cryptosystems.

This is a grocery list in which each fruit is specified together with its calorie content, average price, and maximum count.

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}|>;```

Determine the number of fruits of each type that maximizes the calorie content for a given amount of money.

In[2]:=
`counts = KnapsackSolve[fruits, Quantity[25, "Euros"]]`
Out[2]=

This is the calorie contribution from each of the fruit types and the total.

In[3]:=
`fruits[[All, 1]] counts`
Out[3]=
In[4]:=
```fruits[[All, 1]] counts; Total[%]```
Out[4]=

This is the cost for each fruit type and the total cost.

In[5]:=
`fruits[[All, 2]] counts`
Out[5]=
In[6]:=
```fruits[[All, 2]] counts; Total[%]```
Out[6]=