Knapsack problem/Continuous: Difference between revisions

Content added Content deleted
(→‎version 1: displayed the numbers better, increased precision to three digits, added comments, created a descending sort subroutine (instead of in-line code), indicated {all} when items were taken in entirety.)
Line 1,975: Line 1,975:
Originally used the Fortran program as a prototype.
Originally used the Fortran program as a prototype.
<br>Some amount of code was added to make the output pretty.
<br>Some amount of code was added to make the output pretty.
<lang rexx>/*REXX program solves the burglar's knapsack (continuous) problem. */
<lang rexx>/*REXX program solves the (continuous) burglar's knapsack problem. */
@.= /*═══════ name weight value ══════*/
@.= /*═══════ name weight value ══════*/
@.1 = 'flitch 4 30 '
@.1 = 'flitch 4 30 '
@.2 = 'beef 3.8 36 '
@.2 = 'beef 3.8 36 '
@.3 = 'pork 5.4 43 '
@.3 = 'pork 5.4 43 '
@.4 = 'greaves 2.4 45 '
@.4 = 'greaves 2.4 45 '
@.5 = 'brawn 2.5 56 '
@.5 = 'brawn 2.5 56 '
@.6 = 'welt 3.7 67 '
@.6 = 'welt 3.7 67 '
@.7 = 'ham 3.6 90 '
@.7 = 'ham 3.6 90 '
@.8 = 'salami 3 95 '
@.8 = 'salami 3 95 '
@.9 = 'sausage 5.9 98 '
@.9 = 'sausage 5.9 98 '
parse arg maxW ddig . /*get possible args from the C.L.*/
parse arg maxW d . /*get possible args from the C.L.*/
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
if ddig=='' | ddig==',' then ddig= 2 /*# of decimal digits in FORMAT. */
if d=='' | d==',' then d= 3 /*# of decimal digits in FORMAT. */
wL=length(' weight '); nL=length('total weight'); vL=length(' value ')
wL=d+length('weight'); nL=d+length('total weight'); vL=d+length('value')
totW=0; totV=0
totW=0; totV=0
do j=1 while @.j\==''; parse var @.j n.j w.j v.j .
do #=1 while @.#\==''; parse var @.# n.# w.# v.# .
end /*j*/ /* [↑] assign to separate lists.*/
end /*#*/ /* [↑] assign to separate lists.*/
items=j-1 /*ITEMS: the # of items in @ list*/
#=#-1 /*#: number of items in @ list.*/
call show 'unsorted item list' /*display a header and the @ list*/
call show 'unsorted item list' /*display header and the @ list.*/
/* [↓] sort is OK for short lists*/
call sortD /*invoke using a descending sort.*/
⚫
call hdr "burglar's knapsack contents"
do sorts=2 to items /*sort: descending value/unit wt.*/
⚫
do j=1 for # while totW<maxW; f=1 /*grab items*/
_n=n.sorts; _w=w.sorts; _v=v.sorts /*calc. placeholders for DO loop.*/
do k=sorts-1 by -1 to 1 while v.k/w.k < _v/_w /*order it*/
if totW+w.j>=maxW then f=(maxW-totW)/w.j /*calc fract*/
kp=k+1; n.kp=n.k; w.kp=w.k; v.kp=v.k /*shuffle.*/
totW=totW+w.j*f; totV=totV+v.j*f /*add──►tots*/
⚫
call syf left(word('{all}',1+(f\==1)),5) n.j, w.j*f, v.j*f
⚫
end /*k*/
⚫
end /*j*/ /*↑show item*/
⚫
kp=k+1; n.kp=_n; w.kp=_w; v.kp=_v
end /*sorts*/
call sep; say /* [↓] $ supresses trailing Θs.*/
⚫
call sy left('total weight',nL,'─'), $(format(totW,,d))

⚫
call sy left('total value',nL,'─'), , $(format(totV,,d))
⚫
call hdr "burglar's knapsack contents"
⚫
do j=1 for items while totW < maxW; f=1
if totW+w.j>=maxW then 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 /*j*/
call sep
⚫
call sy left('total weight',nL,'─'), format(totW,,ddig)
⚫
call sy left('total value',nL,'─'), , format(totV,,ddig)
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────one─liner subroutines────────────────────*/
/*──────────────────────────────────one─liner subroutines──────────────────────*/
hdr: say; say center(arg(1),50,'─'); say; call title; call sep; return
hdr: say; say; say center(arg(1),50,'─'); say; 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
show: call hdr arg(1); do j=1 for items; call syf n.j,w.j,v.j;end; say; return
show: call hdr arg(1); do j=1 for #; call syf n.j,w.j,v.j; end; return
sy: say left('',9) left(arg(1),nL) right(arg(2),wL) right(arg(3),vL); return
sy: say left('',9) left(arg(1),nL) right(arg(2),wL) right(arg(3),vL); return
syf: call sy arg(1), format(arg(2),,ddig), format(arg(3),,ddig); return
syf: call sy arg(1), $(format(arg(2),,d)), $(format(arg(3),,d)); return
title: call sy center('item',nL),center("weight",wL),center('value',vL); return</lang>
title: call sy center('item',nL), center("weight",wL), center('value',vL); return
$:x=arg(1);if pos(.,x)>1 then x=left(strip(strip(x,'T',0),,.),length(x));return x
⚫
'''output''' using the default inputs of: &nbsp; <tt> 15 2 </tt>
/*──────────────────────────────────SORTD subroutine───────────────────────────*/
<pre style="height:50ex">
sortD: do sort=2 to #; _n=n.sort; _w=w.sort; _v=v.sort /*descending. */
do k=sort-1 by -1 to 1 while v.k/w.k<_v/_w /*order items.*/
p=k+1; n.p=n.k; w.p=w.k; v.p=v.k /*shuffle 'em.*/
end /*k*/ /*[↓] last one*/
⚫
a=k+1; n.a=_n; w.a=_w; v.a=_v /*place item. */
⚫
end /*sort*/
return /* ↑ ↑ ↑ algorithm is OK for smallish arrays.*/</lang>
⚫
'''output''' using the default inputs of: &nbsp; <tt> 15 3 </tt>
<pre>
────────────────unsorted item list────────────────
────────────────unsorted item list────────────────


item weight value
item weight value
═══════════════ ═════════ ════════
════════════ ════════ ═══════
flitch 4.00 30.00
flitch 4 30
beef 3.80 36.00
beef 3.8 36
pork 5.40 43.00
pork 5.4 43
greaves 2.40 45.00
greaves 2.4 45
brawn 2.50 56.00
brawn 2.5 56
welt 3.70 67.00
welt 3.7 67
ham 3.60 90.00
ham 3.6 90
salami 3.00 95.00
salami 3 95
sausage 5.90 98.00
sausage 5.9 98




───────────burglar's knapsack contents────────────
───────────burglar's knapsack contents────────────


item weight value
item weight value
═══════════════ ═════════ ════════
════════════ ════════ ═══════
salami 3.00 95.00
{all} salami 3 95
ham 3.60 90.00
{all} ham 3.6 90
brawn 2.50 56.00
{all} brawn 2.5 56
greaves 2.40 45.00
{all} greaves 2.4 45
welt 3.50 63.38
welt 3.5 63.378
═══════════════ ═════════ ════════
════════════ ════════ ═══════

total weight 15.00
total value 349.38
total weight─── 15
total value─── 349.378
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"