Anonymous user
Knapsack problem/Continuous: Difference between revisions
m
→{{header|Python}}
(added Fortran) |
|||
Line 607:
TOTAL WEIGHT: 15.00
TOTAL VALUE: 349.38</pre>
=={{header|REXX}}==
Any resemblence to the Fortran code is 120% coincidental.
<lang rexx>
/*REXX program to solve the burglar's knapsack (continuous) problem. */
@.=''
/* name weight value */
@.1='flitch 4 30 '
@.2='beef 3.8 36 '
@.3='pork 5.4 43 '
@.4='greaves 2.4 45 '
@.5='brawn 2.5 56 '
@.6='welt 3.7 67 '
@.7='ham 3.6 90 '
@.8='salami 3 95 '
@.9='sausage 5.9 98 '
nL=length('total weight'); wL=length('weight'); vL=length(' value ')
totW=0; totV=0
do j=1 while @.j\==''
parse var @.j n w v .
nL=max(nL,length(n)); n.j=n
totW=totW+w ; w.j=w
totV=totV+v ; v.j=v
end
items=j-1 /*items is the number of items. */
nL=nL+nL%4 /*nL: max length name + 25%. */
wL=max(wL,length(format(totw,,2))) /*wL: max formatted weight width*/
vL=max(vL,length(format(totv,,2))) /*vL: max formatted value width*/
totW=0; totV=0
call show 'before sorting'
/*sort items by (desending) value per unit weight.*/
do j=2 to items
k=j-1; _n=n.j; _w=w.j; _v=v.j
do k=k by -1 to 1 while v.k/w.k<_v/_w
kp1=k+1; n.kp1=n.k; w.kp1=w.k; v.kp1=v.k
end
kp1=k+1; n.kp1=_n; w.kp1=_w; v.kp1=_v
end /*j*/
call show 'after sorting'
call hdr "burgler's knapsack contents"
maxW=15 /*burgler's knapsack max weight. */
do j=1 for items while totW<maxW
if totW+w.j<maxW then do
totW=totW + w.j
totV=totV + v.j
call syf n.j, w.j, v.j
end
else do
f=(maxW-totW)/w.j
totW=totW + w.j*f
totV=totV + v.j*f
call syf n.j, w.j*f, v.j*f
end
end /*j*/
call sep
call sy left('total weight',nL,'-'), format(totW,,2)
call sy left('total value',nL,'-'), , format(totV,,2)
exit
/*─────────────────────────────────────one-liner subroutines────────────*/
hdr: indent=left('',5); call verse arg(1); call title; call sep; return
sep: call sy copies('=',nL),copies("=",wL),copies('=',vL); return
show: call hdr arg(1); do j=1 for items; call syf n.j,w.j,v.j;end; say; return
sy: say indent left(arg(1),nL) right(arg(2),wL) right(arg(3),vL); return
syf: call sy arg(1),format(arg(2),,2),format(arg(3),,2); return
title: call sy center('item',nL),center("weight",wL),center('value',vL); return
verse: say; say; say center(arg(1),40,'─'); say; return
</lang>
Output:
<pre style="height:30ex;overflow:scroll">
─────────────before sorting─────────────
item weight value
=============== ====== =======
flitch 4.00 30.00
beef 3.80 36.00
pork 5.40 43.00
greaves 2.40 45.00
brawn 2.50 56.00
welt 3.70 67.00
ham 3.60 90.00
salami 3.00 95.00
sausage 5.90 98.00
─────────────after sorting──────────────
item weight value
=============== ====== =======
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.70 67.00
sausage 5.90 98.00
beef 3.80 36.00
pork 5.40 43.00
flitch 4.00 30.00
──────burgler's knapsack contents───────
item weight value
=============== ====== =======
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
=============== ====== =======
total weight--- 15.00
total value--- 349.38
</pre>
=={{header|Tcl}}==
| |||