Essays/IntegerKnapsack
< Essays
Jump to navigation
Jump to search
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).