//! version 1.0 31DEC2018  DIME Analytics bbdaniels@gmail.com

// knapsack - Stata module to solve the 0/1 knapsack problem.

version 12.0

cap prog drop knapsack
prog def knapsack , rclass

syntax ///
  anything(name=budget id="budget constraint") ///
  [if] [in], ///
  Price(varname) Value(varname) ///
  [GENerate(string asis)]

// Setup in Stata

marksample touse

  if("`generate'" != "") {
    gen `generate' = .
  }

  local cols = `budget' + 1
    set matsize 10000

  qui count if `touse'
    local obs = `r(N)'
    local rows = `obs' + 1

  local theLabel : var label `value'

// Mata setup

mata: mata clear
m {

    st_view(v=0,.,"`value'","`touse'")
		v = 0 \ v
  	st_view(w=0,.,"`price'","`touse'")
		w = 0 \ w

// Loop over [budget x items] space to find solutions

  theSolutions = J(`rows',`cols',0)

  for(i=2;i<=`rows';i++) {
    for (j=1;j<=`budget';j++) {
      if(w[i] > j) {
        theSolutions[i,j+1] = theSolutions[i-1,j+1]
      }
      else {
	      opts = theSolutions[i-1, j+1], theSolutions[i-1, j-w[i]+1] + v[i]
        theSolutions[i, j+1] = max(opts)
      }
    }
  }

// Get list of chosen items

  isChosen = J(`rows',1,0)
  theColumn = `cols'
  for(i=`rows';i>1;i--) {
    if(theSolutions[i,theColumn]>theSolutions[i-1,theColumn]) {
      isChosen[i]=1
      theColumn = theColumn - w[i]
      }
  }

// Pass back to Stata

  isChosen = isChosen[|2\.|]

  if("`generate'" != "") {
    st_store(.,"`generate'",isChosen)
  }

  theSolution = theSolutions[`rows',`cols']
  st_matrix("theSolution",theSolution)


// End Mata
  }

// Print the solution in Stata and save to r()

  local theSolution = el(theSolution,1,1)
  return scalar max = `theSolution'
  di in red "Maximum Total `theLabel' = `theSolution'"

// Finish up

  cap mat drop theSolution

end

// Have a lovely day!