Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: simplified a DO loop assignments, changed some indentations.) |
|||
Line 1,645: | Line 1,645: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Any resemblence to the Fortran code is 120% coincidental. |
Any resemblence to the Fortran code is 120% coincidental. |
||
<lang rexx>/*REXX program |
<lang rexx>/*REXX program solves the burglar's knapsack (continuous) problem. */ |
||
@.= /*═══════ name weight value ══════*/ |
|||
@.='' |
|||
⚫ | |||
/*════ name weight value ════*/ |
|||
@. |
@.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 ' |
||
@.9 = 'sausage 5.9 98 ' |
|||
wL=length('weight'); nL=length('total weight'); vL=length(' value ') |
|||
totW=0; totV=0 |
totW=0; totV=0 |
||
do j=1 while @.j\==''; parse var @.j n.j w.j v.j . |
|||
nL=max(nL,length(n.j)) |
|||
totW=totW+w.j |
|||
totV=totV+v.j |
|||
end /*j*/ |
|||
items=j-1 /* |
items=j-1 /*ITEMS is the number of items.*/ |
||
nL=nL+nL%4 /*nL: max length name + 25%. |
nL=nL+nL%4 /*nL: max length name + ≈ 25%.*/ |
||
wL=max(wL,length(format(totw,,2))) /*wL: max formatted weight width*/ |
wL=max(wL,length(format(totw,,2))) /*wL: max formatted weight width*/ |
||
vL=max(vL,length(format(totv,,2))) /*vL: max formatted value width*/ |
vL=max(vL,length(format(totv,,2))) /*vL: max formatted value width*/ |
||
totW=0; totV=0 |
totW=0; totV=0 |
||
call show ' |
call show 'unsorted item list' |
||
do j=2 to items /*sort by desending value/unit wt*/ |
do j=2 to items /*sort by desending value/unit wt*/ |
||
k=j-1; _n=n.j; _w=w.j; _v=v.j |
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 |
do k=k by -1 to 1 while v.k/w.k < _v/_w |
||
kp1=k+1; n.kp1=n.k; |
kp1=k+1; n.kp1=n.k; w.kp1=w.k; v.kp1=v.k |
||
end /*k*/ |
end /*k*/ |
||
kp1=k+1; n.kp1=_n; w.kp1=_w; v.kp1=_v |
kp1=k+1; n.kp1=_n; w.kp1=_w; v.kp1=_v |
||
end /*j*/ |
end /*j*/ |
||
call show 'after sorting' |
|||
call hdr "burgler's knapsack contents" |
call hdr "burgler's knapsack contents" |
||
maxW=15 /*burgler's knapsack max weight. */ |
maxW=15 /*burgler's knapsack max weight. */ |
||
Line 1,700: | Line 1,698: | ||
call sy left('total value',nL,'─'), , format(totV,,2) |
call sy left('total value',nL,'─'), , format(totV,,2) |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────one─liner |
/*──────────────────────────────────one─liner subroutines────────────────────*/ |
||
hdr: indent=left('',9); call verse arg(1); call title; call sep; return |
hdr: indent=left('',9); call verse arg(1); call title; call sep; return |
||
sep: call sy copies('═',nL), copies("═",wL), copies('═',vL); return |
sep: call sy copies('═',nL), copies("═",wL), copies('═',vL); return |
||
Line 1,710: | Line 1,708: | ||
'''output''' |
'''output''' |
||
<pre style="height:50ex"> |
<pre style="height:50ex"> |
||
────────────────unsorted item list──────────────── |
|||
──────────────────before sorting────────────────── |
|||
item weight value |
item weight value |
||
Line 1,723: | Line 1,721: | ||
salami 3.00 95.00 |
salami 3.00 95.00 |
||
sausage 5.90 98.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 |
|||
⚫ | |||