Wolfram Language & System 11.0 (2016)|Legacy Documentation

This is documentation for an earlier version of the Wolfram Language.View current documentation (Version 11.2)

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.

DetailsDetails

  • KnapsackSolve finds a list {c1,c2,} of non-negative integer counts cimaxcounti 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.

ExamplesExamplesopen allclose all

Basic Examples  (4)Basic Examples  (4)

Find the maximum number ci of items with respective costs 4, 2, and 3, satisfying :

In[1]:=
Click for copyable input
Out[1]=

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

In[1]:=
Click for copyable input
Out[1]=

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

In[1]:=
Click for copyable input
Out[1]=

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

In[2]:=
Click for copyable input
Out[2]=

Use an association to label the sets of items:

In[1]:=
Click for copyable input
Out[1]=
Introduced in 2016
(11.0)