# 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).