link printf

global wants                    # items wanted for knapsack

procedure main(A) # kanpsack 0-1
   if !A == ("--trace"|"-t") then &trace := -1     # trace everything (debug)
   if !A == ("--memoize"|"-m") then m :=: Memo_m   # hook (swap) procedure

   printf("Knapsack-0-1: with maximum weight allowed=%d.\n",maxw  := 400)
   showwanted(wants := get_wants())
   showcontents(bag := m(*wants,maxw))
   printf("Performance: time=%d ms collections=%d\n",&time,&collections)
end

record packing(items,weight,value)

procedure Memo_m(i,w)           #: Hook procedure to memoize the knapsack
static memoT
initial memoT := table()
   return \memoT[k := i||","||w] | ( memoT[k] := Memo_m(i,w) )
end

procedure m(i,w)                #: Solve the Knapsack 0-1 as per Wikipedia
static nil
initial nil := packing([],0,0)
   if 0 = (i | w) then
      return nil
   else if wants[i].weight > w then
           return m(i-1, w)
        else {
            x0 := m(i-1,w)
            x1 := m(i-1,w-wants[i].weight)
            if ( x1.value + wants[i].value) > x0.value then
               return packing(x1.items ||| wants[i].items,
                              x1.weight + wants[i].weight,
                              x1.value + wants[i].value)
            else
               return x0
        }
end

procedure showwanted(wants)     #: show the list of wanted items
   every (tw := 0) +:= (!wants).weight
   printf("Packing list has total weight=%d and includes %d items [",tw,*wants)
   every printf(" %s",!(!wants).items|"]\n")
end

procedure showcontents(bag)     #: show the list of the packed bag
   printf("The bag weighs=%d holding %d items [",bag.weight,*bag.items)
   every printf(" %s",!bag.items|"]\n")
end

procedure get_wants()           #: setup list of wanted items
   return  [ packing(["map"], 9, 150),
             packing(["compass"], 13, 35),
             packing(["water"], 153, 200),
             packing(["sandwich"], 50, 160),
             packing(["glucose"], 15, 60),
             packing(["tin"], 68, 45),
             packing(["banana"], 27, 60),
             packing(["apple"], 39, 40),
             packing(["cheese"], 23, 30),
             packing(["beer"], 52, 10),
             packing(["suntan cream"], 11, 70),
             packing(["camera"], 32, 30),
             packing(["T-shirt"], 24, 15),
             packing(["trousers"], 48, 10),
             packing(["umbrella"], 73, 40),
             packing(["waterproof trousers"], 42, 70),
             packing(["waterproof overclothes"], 43, 75),
             packing(["note-case"], 22, 80),
             packing(["sunglasses"], 7, 20),
             packing(["towel"], 18, 12),
             packing(["socks"], 4, 50),
             packing(["book"], 30, 10) ]
end