111 lines
2.3 KiB
Plaintext
111 lines
2.3 KiB
Plaintext
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
|