type KnapSackItem string name,sys dag,value,tag

KnapSackItem it[100]

sys dmax=400
sys items=22

it=>

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

tot=0
for i=1 to items
  tot+=it(i).dag
next
xs=tot-dmax

'REMOVE LOWEST PRIORITY ITEMS TILL XS<=0

cr=chr(13)+chr(10)
tab=chr(9)
pr="remove: " cr
c=0

do
  v=1e9
  w=0
  k=0
  '
  'FIND NEXT LEAST VALUE ITEM
  '
  for i=1 to items
    if it[i].tag=0
      'w=it[i].value               'TEST PRIORITY ONLY
      w=1000*it[i].value/it[i].dag 'TEST PRIORIT/WEIGHT VALUE
      if w<v then v=w : k=i
    end if
  next
  '
  'LOG AND REMOVE FROM LIST
  '
  if k
    xs-=it[k].dag 'deduct from excess weight
    it[k].tag=1
    pr+=it(k).name tab it(k).dag tab it(k).value cr
    if xs<=0 then exit do 'Weight within dmax
  end if
  c++
  if c>=items then exit do
end do
'
pr+=cr "Knapsack contents: " cr
'
for i=1 to items
  if it(i).tag=0
    pr+=it(i).name tab it(i).dag tab it(i).value cr
  end if
next

'TRY FITTING IN LOWER PRIORITY ITEMS

av=-xs

for i=1 to items
  if it[i].tag
    if av-it[i].dag > 0 then
      pr+="Can include: " it(i).name tab it(i).dag tab it(i).value cr
      av-=it[i].dag
    end if
  end if
next
pr+=cr "Weight: " dmax+xs
'putfile "s.txt",pr
print pr
'Knapsack contents:
'map             	9	150
'compass         	13	35
'water           	153	200
'sandwich        	50	160
'glucose         	15	60
'banana          	27	60
'suntan cream     	11	70
'waterproof trousers	42	70
'waterproof overclothes	43	75
'note-case        	22	80
'sunglasses       	7	20
'socks           	4	50
'
'Weight: 396