KnapsackSolve

KnapsackSolve[{cost1,cost2,…},maxtotalcost]

solves the knapsack problem of finding the maximum number of items associated with each of the costi, subject to the constraint that the total cost is not larger than maxtotalcost.

KnapsackSolve[{{payoff1,cost1},{payoff2,cost2},…},maxtotalcost]

finds a number of items that maximizes the total payoff, while satisfying the constraint on the total cost.

KnapsackSolve[{{payoff1,cost1,maxcount1},…},maxtotalcost]

allows at most maxcounti copies of item i.

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost}]

finds a result that gives a total payoff not larger than maxtotalpayoff.

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost,maxtotalcount}]

adds the constraint of having no more than maxtotalcount items in total.

KnapsackSolve[label1itemspec1,…,maxtotals]

labels each type of item and gives the result as an association.

Details

  • KnapsackSolve finds a list {c1,c2,…} of non-negative integer counts ci≤maxcounti that maximizes the total payoff and satisfies the constraints specified by maxtotals.
  • All payoffs and costs must be non-negative real numbers or Quantity objects. Counts must be non-negative integers or Infinity.
  • Possible specifications for the constraints maxtotals are: maxtotalcost, {maxtotalcost}, {maxtotalpayoff,maxtotalcost}, and {maxtotalpayoff,maxtotalcost,maxtotalcount}.
  • By default, payoffi is taken to be 1, and maximum constraints are taken to be Infinity.
  • KnapsackSolve solves the unbounded knapsack problem if the maxcounti are omitted or Infinity, the bounded knapsack problem if they are non-negative integers, and the 0-1 knapsack problem if they are all 1.
  • Each collection {payoffi,costi,maxcounti} can alternatively be given as <|"Payoff"->payoffi,"Cost"->costi,"MaxCount"->maxcounti|>, 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.

Examples

open allclose all

Basic Examples  (4)

Find the numbers of items ci maximizing the total count c1+c2+c3 and satisfying :

Find the numbers of items c1 and c2 maximizing the total payoff 3c1+2c2 and satisfying :

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

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

Use an association to label the sets of items:

Scope  (13)

Profits, Costs, and Individual Counts  (6)

Solve the knapsack problem by specifying costs only:

Omitted payoffs are set to 1 by default:

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

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

Name the payoffs, costs, and maximum individual counts:

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

Use Association instead of a list of rules:

Name the sets of items:

Use Association instead of a list of rules:

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

Constraints on the Totals  (4)

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

Specify constraints on the total payoff and total cost:

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

Name the constraints:

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

Use Association instead of a list of rules:

Quantity and QuantityArray  (2)

Use Quantity objects to specify the payoffs or costs:

Compatible units are automatically converted:

Solve a knapsack problem with QuantityArray objects:

Dataset  (1)

Use Dataset objects to specify the collection of items:

Applications  (1)

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

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

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

Properties & Relations  (5)

KnapsackSolve is equivalent to a form of LinearProgramming:

If not specified, the values of the total payoff and total count are set to Infinity:

Setting maxtotalpayoff to Infinity will return the maximum total a solution can reach:

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

KnapsackSolve returns only one solution satisfying the constraints:

But other solutions can exist:

Wolfram Research (2016), KnapsackSolve, Wolfram Language function, https://reference.wolfram.com/language/ref/KnapsackSolve.html.

Text

Wolfram Research (2016), KnapsackSolve, Wolfram Language function, https://reference.wolfram.com/language/ref/KnapsackSolve.html.

CMS

Wolfram Language. 2016. "KnapsackSolve." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/KnapsackSolve.html.

APA

Wolfram Language. (2016). KnapsackSolve. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/KnapsackSolve.html

BibTeX

@misc{reference.wolfram_2024_knapsacksolve, author="Wolfram Research", title="{KnapsackSolve}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/KnapsackSolve.html}", note=[Accessed: 25-April-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_knapsacksolve, organization={Wolfram Research}, title={KnapsackSolve}, year={2016}, url={https://reference.wolfram.com/language/ref/KnapsackSolve.html}, note=[Accessed: 25-April-2024 ]}