66 lines
2.3 KiB
Text
66 lines
2.3 KiB
Text
|
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%
|