Essays/IntegerKnapsack

Given a list of integers and a goal G, pick a subset of the integers that adds to G. This is the Integer Knapsack Problem.
The program iknapsack solves the integer knapsack problem.

NB. Integer knapsack problem.
NB. x is the list of numbers, y is goal[,result type]. Result is:
NB. If result type=0 or omitted: 0 if impossible, 1 if possible
NB. if result type=1: empty if impossible, or a mask of inputs with 1 for a combination that works
NB. if result type=2: empty table if impossible, or a table of all solutions, where each row is a
NB.   mask of inputs with 1 for a combination that works
NB. Uses space of ($x) * >:y
iknapsack =: 4 : 0"1 1
'goal type' =. 2 {. y
NB. Fast version if we only want yes/no answer: like the full version,
NB. but we keep only the last line calculated rather than the full table, and
NB. the return success/failure
if. type = 0 do. {: (] +. |.!.0)&:>/&(,&(<(>:goal) {. 1)) (<"0-x) return. end.
NB. Full version giving results:
NB. Create an array where each row i tells which positions
NB. can be reached using inputs from i to the end.  The last row signifies
NB. that is is possible to reach a goal of 0 using no numbers.
reachable =. > (] +. |.!.0)&.>/\.&(,&(<(>:goal) {. 1)) (<"0-x)
NB. If the goal is unreachable, exit empty
if. -. (<0 _1) { reachable do. (type {. 0,#x) $ 0 return. end.
if. type = 2 do.
  NB. The full version, returning the entire table of successes
  NB. Utility: x is the numbers; y is table of feasible masks, meaning that
  NB. each row of y has a selection of the early numbers that leaves the problem
  NB. solvable.  Result is table: for each row of y, the subgoals that must be
  NB. reachable if this row is (not taken),(taken)
  NB. We have reversed each row to make the goal column 0.  This way we don't need to
  NB. know the actual goal at this point.  If the total of the numbers picked in a row of
  NB. y is p, p{nextrow is 1 if the goal can be reached without using this number, and
  NB. (p+this number){nextrow is 1 if the goal can be reached using this number.
  NB.   So the result here is (total of previous rows) + (0,size of this number).
  NB. We fetch (previous numbers),(this number) for the computation.
  NB. It might be better to append the total of previous numbers to the input
  NB. here, to avoid recomputing it.  But then the lists would not be Boolean.
  numsneeded =. ] (+/"1@:(# }:) ([ ,"0 +) {:@]) ({.~ >:@{:@$)
  NB. Utility: y is the mask of selections of previous rows to make the goal reachable; x is
  NB. the list of feasible values using this and succeeding rows.  Result has one column added
  NB. to each row of y, giving the feasible mask including the current row.  Since each
  NB. row of y represents a feasible combination, each row of input will produce 1 or 2
  NB. rows of the result, with 0 and/or 1 appended according as the current number
  NB. can be used or not-used.  If numsneeded asks for an index beyond the goal,
  NB. use 0 (accommodated by clamping the index and giving x an extra 0)
  nextallowed =. ] ((#~ +/"1) ,. (#   0 1 $~ #)@,@]) (((<. #)~ { (0 ,~ [))   x&numsneeded)
else.
  NB. If we need only 1 solution, much simpler: see if the problem can be solved
  NB. without the new number, and return 0 if so, 1 if not.
  NB. y is the mask of selections of previous rows to make the goal reachable; x is
  NB. the list of feasible values using this and succeeding rows. 
  nextallowed =. ] , -.@({~ x&([: +/ ] # ({.~ #)))
end.
NB. Find the solutions, processing the numbers from first to last.
NB. Since we know that the goal is reachable, we discard the
NB. first row of 'reachable', and start with an input that signifies that the problem
NB. is feasible using no inputs before the first one.  Then, we reverse rows of 'reachable'
NB. so as to process first-to-last using /, and we reverse the columns as called for by
NB. 'numsneeded'.
NB. Result is the requested solutions.
nextallowed&:>/&(,&(<(1 0 {.~ -type)$0)) <"1;.0 }. reachable
)
   20 15 10 5 5 iknapsack 25
0 1 0 1 1
0 1 1 0 0
1 0 0 0 1
1 0 0 1 0

The result shows that the goal can be reached with {15,5,5}, (15,10}, or {20,5} (two ways).