HIMEM = PAGE + 8000000
      nItems% = 22
      maxWeight% = 400

      DIM Tag{ivalue%, list%(nItems%-1), lp%}
      DIM items{(nItems%-1)name$, weight%, ivalue%}
      FOR item% = 0 TO nItems%-1
        READ items{(item%)}.name$, items{(item%)}.weight%, items{(item%)}.ivalue%
      NEXT

      DATA "map", 9, 150, "compass", 13, 35, "water", 153, 200, "sandwich", 50, 160
      DATA "glucose", 15, 60, "tin", 68, 45, "banana", 27, 60, "apple", 39, 40
      DATA "cheese", 23, 30, "beer", 52, 10, "suntan cream", 11, 70, "camera", 32, 30
      DATA "t-shirt", 24, 15, "trousers", 48, 10, "umbrella", 73, 40, "book", 30, 10
      DATA "waterproof trousers", 42, 70, "waterproof overclothes", 43, 75
      DATA "note-case", 22, 80, "sunglasses", 7, 20, "towel", 18, 12, "socks", 4, 50

      carry% = FN_Knapsack(items{()}, nItems% - 1, maxWeight%, cache{()})
      FOR i% = 0 TO cache{(carry%)}.lp%-1
        n% = cache{(carry%)}.list%(i%)
        TotalWeight% += items{(n%)}.weight%
        TotalValue% += items{(n%)}.ivalue%
        PRINT items{(n%)}.name$ " "
      NEXT
      PRINT '"Total weight = " ; TotalWeight%
      PRINT "Total value  = " ; TotalValue%
      END

      DEF FN_Knapsack(i{()}, i%, w%, RETURN m{()})
      LOCAL included{}, excluded{}, tmp%, index%
      DIM m{(16384)} = Tag{}, included{} = Tag{}, excluded{} = Tag{}

      index% = i% << 9 OR w%
      IF m{(index%)}.ivalue% THEN = index%

      IF i% = 0 THEN
        IF i{(0)}.weight% > w% THEN
          m{(index%)}.ivalue% = 0 : REM Item doesn't fit
        ELSE
          m{(index%)}.ivalue% = i{(0)}.ivalue%
          m{(index%)}.list%(m{(index%)}.lp%) = 0
          m{(index%)}.lp% += 1
        ENDIF
        = index%
      ENDIF

      tmp% = FN_Knapsack(i{()}, i% - 1, w%, m{()})
      excluded{} = m{(tmp%)}
      IF i{(i%)}.weight% > w% THEN
        m{(index%)} = excluded{} : REM Item weighs too much
        = index%
      ELSE
        tmp% = FN_Knapsack(i{()}, i% - 1, w% - i{(i%)}.weight%, m{()})
        included{} = m{(tmp%)}
        included.ivalue% += i{(i%)}.ivalue%
        included.list%(included.lp%) = i%
        included.lp% += 1
      ENDIF

      IF included.ivalue% > excluded.ivalue% THEN
        m{(index%)} = included{}
      ELSE
        m{(index%)} = excluded{}
      ENDIF
      = index%