Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
(added Fortran) |
|||
Line 607: | Line 607: | ||
TOTAL WEIGHT: 15.00 |
TOTAL WEIGHT: 15.00 |
||
TOTAL VALUE: 349.38</pre> |
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}}== |
=={{header|Tcl}}== |