My version. I didn't want to enumerate all the cases, in case part 2
doubled the number of jugs:
NB. Read in data, convert to list
i =: ".;._2 (#~ (LF,LF) -.@:E. ]) wd 'clippaste'
NB. Integer knapsack problem.
iknapsack =: 4 : 0
reachable =. > (] +. |.!.0)&.>/\.&(,&(<(>:y) {. 1)) (<"0-x)
numsneeded =. ] (+/"1@:(# }:) ([ ,. +) {:@]) ({.~ >:@{:@$)
nextallowed =. ] ((#~ +/"1) ,. (# 0 1 $~ #)@,@]) (((<. #)~ { (0 ,~ [))
x&numsneeded)
nextallowed&:>/&(,&(<1 0$0)) <"1;.0 }. reachable
)
NB. Part 1
# solutions =: i iknapsack 150
NB. Part 2
numminsolutions =: (+/@:= <./) +/"1 solutions
Commentary at http://code.jsoftware.com/wiki/Essays/IntegerKnapsack
Henry Rich
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
