({{, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[{(Subscript[cost, 1]),(Subscript[cost, 2]),…},maxtotalcost]
solves the knapsack problem of finding the maximum number of items associated with each of the (Subscript[cost, i]), subject to the constraint that the total cost is not larger than maxtotalcost.}, {, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[{{(Subscript[payoff, 1]),(Subscript[cost, 1])},{(Subscript[payoff, 2]),(Subscript[cost, 2])},…},maxtotalcost]
finds a number of items that maximizes the total payoff, while satisfying the constraint on the total cost.}, {, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[{{(Subscript[payoff, 1]),(Subscript[cost, 1]),(Subscript[maxcount, 1])},…},maxtotalcost]
allows at most (Subscript[maxcount, i]) copies of item i.}, {, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[items,{maxtotalpayoff,maxtotalcost}]
finds a result that gives a total payoff not larger than maxtotalpayoff.}, {, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[items,{maxtotalpayoff,maxtotalcost,maxtotalcount}]
adds the constraint of having no more than maxtotalcount items in total. }, {, (RefLink[KnapsackSolve, paclet:ref/KnapsackSolve])[\[LeftAssociation](Subscript[label, 1])->(Subscript[itemspec, 1]),…\[RightAssociation],maxtotals]
labels each type of item and gives the result as an association.}})

OpenersNotesSection(Spacer1)Details

(RefLink[KnapsackSolve, paclet:ref/KnapsackSolve]) finds a list {(Subscript[c, 1]),(Subscript[c, 2]),…} of non-negative integer counts (Subscript[c, i])≤(Subscript[maxcount, i]) that maximizes the total payoff and satisfies the constraints specified by maxtotals.

All payoffs and costs must be non-negative real numbers or (RefLink[Quantity, paclet:ref/Quantity]) objects. Counts must be non-negative integers or (RefLink[Infinity, paclet:ref/Infinity]).

Possible specifications for the constraints maxtotals are: maxtotalcost, {maxtotalcost}, {maxtotalpayoff,maxtotalcost}, and {maxtotalpayoff,maxtotalcost,maxtotalcount}.

By default, (Subscript[payoff, i]) is taken to be 1, and maximum constraints are taken to be (RefLink[Infinity, paclet:ref/Infinity]).

(RefLink[KnapsackSolve, paclet:ref/KnapsackSolve]) solves the unbounded knapsack problem if the (Subscript[maxcount, i]) are omitted or (RefLink[Infinity, paclet:ref/Infinity]), the bounded knapsack problem if they are non-negative integers, and the 0-1 knapsack problem if they are all 1.

Each collection {(Subscript[payoff, i]),(Subscript[cost, i]),(Subscript[maxcount, i])} can alternatively be given as <|"Payoff"->(Subscript[payoff, i]),"Cost"->(Subscript[cost, i]),"MaxCount"->(Subscript[maxcount, i])|>, where the entries "Payoff" and "MaxCount" are optional.

The constraint parameters {maxtotalpayoff,maxtotalcost,maxtotalcount} can alternatively be given as <|"MaxTotalPayoff"->maxtotalpayoff,"MaxTotalCost"->maxtotalcost,"MaxTotalCount"->maxtotalcount|>, where the entries "MaxTotalPayoff" and "MaxTotalCount" are optional.

OpenersPrimaryExamplesSection(Spacer1)Examples  (22)

OpenersExampleSection0(Spacer1)Basic Examples  (4)

Find the maximum number (Subscript[c, i]) of items with respective costs 4, 2, and 3, satisfying 4 (Subscript[c, 1])+2 (Subscript[c, 2])+3 (Subscript[c, 3])≤9:

KnapsackSolve[{4,2,3},9]

Find the numbers of items (Subscript[c, 1]) and (Subscript[c, 2]) maximizing the total payoff 3(Subscript[c, 1])+2(Subscript[c, 2]) and satisfying 4 (Subscript[c, 1])+5(Subscript[c, 2])≤10:

KnapsackSolve[{{3,4},{2,5}},10]

Solve the knapsack problem for two sets of payoffs, costs, and maximum counts:

KnapsackSolve[{{3,2,7},{2,1,5}},10]

Solve the problem with additional constraints on the total payoff and total count:

KnapsackSolve[{{3,2,7},{2,1,5}},{15,10,5}]

Use an association to label the sets of items:

KnapsackSolve[<|"apples"->{8,3,3},"oranges"->{9,7,5}|>,25]

OpenersExampleSection1(Spacer1)Scope  (12)

OpenersExampleSubsection0(Spacer1)Profits, Costs, and Individual Counts  (6)

Solve the knapsack problem by specifying costs only:

KnapsackSolve[{4,2,3},11]

Omitted payoffs are set to 1 by default:

%===KnapsackSolve[{{1,4},{1,2},{1,3}},11]

Solve the knapsack problem, specifying values for payoffs and costs:

KnapsackSolve[{{5,4},{3,3},{7,8}},26]

The 0-1 knapsack problem is obtained by setting all maximum individual counts to 1:

KnapsackSolve[{{5.2,4,1},{3,3.5,1},{7,8,1}},30]

Name the payoffs, costs, and maximum individual counts:

KnapsackSolve[{{"Payoff"->4,"Cost"->12},{"Payoff"->5,"Cost"->13,"MaxCount"->2}},45]

The key-value pairs can be given in any order:

KnapsackSolve[{{"Cost"->12,"Payoff"->4},{"MaxCount"->2,"Cost"->13,"Payoff"->5}},45]

Use (RefLink[Association, paclet:ref/Association]) instead of a list of rules:

KnapsackSolve[{<|"Cost"->12,"Payoff"->4|>,<|"MaxCount"->2,"Cost"->13,"Payoff"->5|>},45]

Name the sets of items:

KnapsackSolve[{"forks"->{3,4},"spoons"->{2,3,2}},{30,30}]

Use (RefLink[Association, paclet:ref/Association]) instead of a list of rules:

KnapsackSolve[<|"forks"->{3,4},"spoons"->{2,3,2}|>,{30,30}]

Name both the sets of items and the payoffs, costs, and maximum individual counts:

KnapsackSolve[{"forks"-><|"Payoff"->3,"Cost"->4|>,"spoons"-><|"Payoff"->2,"Cost"->3,"MaxCount"->2|>},{30,30,5}]

OpenersExampleSubsection1(Spacer1)Constraints on the Totals  (4)

Solve the knapsack problem with a constraint on the total cost:

KnapsackSolve[{{6,8},{3,4,5},{4,6}},30]

Specify constraints on the total payoff and total cost:

KnapsackSolve[<|a->{2,1},b->{4,3,5},c->{3,2,2}|>,{15,30}]

Constrain the total payoff, total cost, and total count:

KnapsackSolve[{{10,1},{8,2,20},{9,7,6}},{25,30,10}]

Name the constraints:

KnapsackSolve[{{8,9,2},{4,4,5},{5,6}},{"MaxTotalPayoff"->35,"MaxTotalCost"->30}]

The key-value pairs can be given in any order:

KnapsackSolve[{{8,9,2},{4,4,5},{5,6}},{"MaxTotalCost"->30,"MaxTotalPayoff"->35}]

Use (RefLink[Association, paclet:ref/Association]) instead of a list of rules:

KnapsackSolve[{{8,9,2},{4,4,5},{5,6}},<|"MaxTotalCost"->30,"MaxTotalCount"->4,"MaxTotalPayoff"->35|>]

OpenersExampleSubsection2(Spacer1)Quantity and QuantityArray  (2)

Use (RefLink[Quantity, paclet:ref/Quantity]) objects to specify the payoffs or costs:

KnapsackSolve[{{Quantity[3,"USDollars"],2,7},{Quantity[2,"USDollars"],1,5}},{Quantity[15,"USDollars"],30,15}]

Compatible units are automatically converted:

KnapsackSolve[{{8,Quantity[52,"Seconds"]},{10,Quantity[1,"Minutes"]}},Quantity[MixedMagnitude[{23,42}],MixedUnit[{"Minutes","Seconds"}]]]

Solve a knapsack problem with (RefLink[QuantityArray, paclet:ref/QuantityArray]) objects:

KnapsackSolve[QuantityArray[{{3,2,7},{2,1,5}},{"USDollars","Minutes","DimensionlessUnit"}],QuantityArray[{15,30,15},{"USDollars","Minutes","DimensionlessUnit"}]]

OpenersExampleSection3(Spacer1)Applications  (1)

Maximize the calorie content of fruits in a grocery list of a limited amount of money:

items=<|(Entity["apple", Entity["FoodType","Apple"], "Entity[\"FoodType\", \"Apple\"]", "food type"])->{(Quantity[91, "Cal", dietary Calories, "LargeCalories"]),(QuantityPrefix["2.36", "€" , euros, "Euros"]),3},(Entity["orange", Entity["FoodType","Orange"], "Entity[\"FoodType\", \"Orange\"]", "food type"]) ->{(Quantity[71, "Cal", dietary Calories, "LargeCalories"]),(QuantityPrefix["2.12", "€" , euros, "Euros"])},(Entity["banana", Entity["FoodType","Banana"], "Entity[\"FoodType\", \"Banana\"]", "food type"])->{(Quantity[105, "Cal", dietary Calories, "LargeCalories"]),(QuantityPrefix["1.89", "€" , euros, "Euros"]),5},(Entity["kiwi", Entity["FoodType","Kiwi"], "Entity[\"FoodType\", \"Kiwi\"]", "food type"])->{(Quantity[103, "Cal", dietary Calories, "LargeCalories"]),(QuantityPrefix["3.77", "€" , euros, "Euros"])},(Entity["pear", Entity["FoodType","Pear"], "Entity[\"FoodType\", \"Pear\"]", "food type"])->{(Quantity[96, "Cal", dietary Calories, "LargeCalories"]),(QuantityPrefix["2.87", "€" , euros, "Euros"])}|>;

counts=KnapsackSolve[items,(QuantityPrefix[25, "€" , euros, "Euros"])]

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

items[[All,1]]counts

Total[%]

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

items[[All,2]]counts

Total[%]

OpenersExampleSection4(Spacer1)Properties & Relations  (5)

(RefLink[KnapsackSolve, paclet:ref/KnapsackSolve]) is equivalent to a form of (RefLink[LinearProgramming, paclet:ref/LinearProgramming]):

sets={{1.,2.,1},{3.,4.,5},{2.,3.,2}};
maxtotalcost=10.;

KnapsackSolve[sets,maxtotalcost]

data=Transpose[sets];

LinearProgramming[-data[[1]],{data[[2]]},{{maxtotalcost,-1}},{0, #}& /@ data[[3]],Integers]

If not specified, the values of the total payoff and total count are set to (RefLink[Infinity, paclet:ref/Infinity]):

assoc=<|a->{2,1},b->{4,3,5},c->{3,2,2}|>;
KnapsackSolve[assoc,15]===KnapsackSolve[assoc,{Infinity,15,Infinity}]

Setting maxtotalpayoff to (RefLink[Infinity, paclet:ref/Infinity]) will return the maximum total a solution can reach:

KnapsackSolve[{{8,1},{6,2,20},{9,7,6}},{Infinity,30,5}]

The costs and payoffs can be non-negative real numbers, but the counts must be positive integers:

list={a->{2.5,2.1,3},b->{4.1,3.4,5},c->{3.2,2.7,2}};
KnapsackSolve[list,20.5]

(RefLink[KnapsackSolve, paclet:ref/KnapsackSolve]) returns only one solution satisfying the constraints:

sets={{28,20},{11,17},{16,15},{22,18}};
maxtotalcost=72;
sol=KnapsackSolve[sets,maxtotalcost]

{payoffs,costs}=Transpose[sets]

solpof=sol.payoffs

But other solutions can exist:

altsol={2,0,2,0};
altsol.payoffs==solpof
altsol.costs≤maxtotalcost

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[LinearProgramming, paclet:ref/LinearProgramming])  ▪  (RefLink[ArgMax, paclet:ref/ArgMax])  ▪  (RefLink[Maximize, paclet:ref/Maximize])  ▪  (RefLink[NMaximize, paclet:ref/NMaximize])  ▪  (RefLink[FindMaximum, paclet:ref/FindMaximum])  ▪  (RefLink[FrobeniusSolve, paclet:ref/FrobeniusSolve])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Diophantine Equations, paclet:guide/DiophantineEquations])}, {▪(RefLinkPlain[Optimization, paclet:guide/Optimization])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}})}})