Skip to content

Knapsack solver

Stata can now solve constrained optimization problems of the "knapsack" variety! Given a budget constraint and a dataset of items with prices and values, knapsack will calculate the most valuable obtainable combination under the given budget, and returns those items and their total value. Here's an example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
. sysuse auto.dta, clear
(1978 Automobile Data)

. keep mpg price
. rename (mpg price)(cost value)

. knapsack 500, p(cost) v(value) gen(chosen)
(74 missing values generated)
Maximum Total Price = 253853

. di "`r(max)'"
253853

. table chosen , c(sum cost sum value)
----------------------------------
   chosen |  sum(cost)  sum(value)
----------+-----------------------
        0 |       1076      202376
        1 |        500      253853
----------------------------------

knapsack is available on SSC and is open for development on GitHub. Submit bugs and feature requests here. If you like knapsack, be sure to visit my homepage and Stata boilerplate code.