Knapsack problem/Continuous: Difference between revisions

Line 2,248:

Originally used the Fortran program as a prototype.

<br>Some amount of code was added to make the output pretty.

<lang rexx>/*REXX program solves the (continuous) burglar's knapsack 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 '

parse arg maxW d . /*get possible ~~args~~ from the C.L.*/

parse arg maxW d . /*get possible arguments from the C.L. */

if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack ~~max~~ weight. */

if maxW=='' | maxW==',' then maxW=15 /*the burglar's knapsack maximum weight*/

if d=='' | d==',' then d= 3 /*# of decimal digits in FORMAT. */

if d=='' | d==',' then d= 3 /*number of decimal digits in FORMAT. */

wL=d+length('weight'); nL=d+length('total weight'); vL=d+length('value')

totW=0; totV=0

do #=1 while @.#\==''; parse var @.# n.# w.# v.# .

end /*#*/ /* [↑] assign to separate lists.*/

end /*#*/ /* [↑] assign item to separate lists. */

#=#-1 /*#: number of items in @ list.*/

#=#-1 /*#: is the number of items in @ list.*/

call show 'unsorted item list' /*display header and the @ list.*/

call show 'unsorted item list' /*display the header and the @ list.*/

call sortD /*invoke ~~using~~ a ~~descending~~ ~~sort~~.*/

call sortD /*invoke sort (which sorts descending).*/

call hdr "burglar's knapsack contents"

do j=1 for # while totW<maxW; f=1 /*~~grab~~ items*/

do j=1 for # while totW<maxW; f=1 /*process items. */

if totW+w.j>=maxW then f=(maxW-totW)/w.j /*~~calc~~ fract*/

if totW+w.j>=maxW then f=(maxW-totW)/w.j /*calculate fract.*/

totW=totW+w.j*f; totV=totV+v.j*f /*~~add──►tots~~*/

totW=totW+w.j*f; totV=totV+v.j*f /*add ───► totals.*/

call syf left(word('{all}',1+(f\==1)),5) n.j, w.j*f, v.j*f

end /*j*/ /*~~↑show~~ item*/

end /*j*/ /* [↑] show item.*/

call sep; say /* [↓] $ ~~supresses~~ trailing Θs.*/

call sep; say; t='t' /* [↓] $ suppresses trailing zeroes.*/

call sy left('total weight',nL,'─'), $(format(totW,,d))

call sy left('total value',nL,'─'), , $(format(totV,,d))

exit /*stick a fork in it, we're done.*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────one─liner ~~subroutines──────────────────────~~*/

/*──────────────────────────────────one─liner subroutines─────────────────────*/

hdr: say; say; say center(arg(1),50,'─'); say; call title; call sep; return

sep: call sy copies('═',nL), copies("═",wL), copies('═',vL); 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

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

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

$: x=arg(1);if pos(.,x)>1 then x=left(strip(strip(x,t,0),,.),length(x));return x

/*──────────────────────────────────SORTD ~~subroutine───────────────────────────~~*/

/*──────────────────────────────────SORTD subroutine──────────────────────────*/

sortD: do ~~sort~~=2 to #; _n=n.~~sort~~; _w=w.~~sort~~; ~~_v=v.sort~~ /*descending. */

sortD: do s=2 to #; a=n.s; !=w.s; u=v.s /* [↓] this is a descending sort.*/

do k=~~sort~~-1 by -1 to 1 while v.k/w.k<_v/~~_w /*order items~~.*/

do k=s-1 by -1 to 1 while v.k/w.k<u/!;?=k+1;n.?=n.k;w.?=w.k;v.?=v.k;end

p=k+1; n.p=~~n.k~~; w.p=~~w.k~~; v.p=~~v.k /*shuffle 'em.*/~~

?=k+1; n.?=a; w.?=!; v.?=u

end /*~~k*/ /*[↓] last one~~*/

end /*s*/

~~a=k+1;~~ ~~n.a=_n;~~ ~~w.a=_w;~~ ~~v.a=_v~~ ~~/*place item~~. */

return /* ↑↑↑ sort algorithm is OK for small arrays.*/</lang>

⚫

'''output''' using the default inputs of:   <tt> 15   3 </tt>

end /*sort*/

return /* ↑ ↑ ↑ algorithm is OK for smallish arrays.*/</lang>

⚫

'''output''' using the default inputs of:   <tt> 15 3 </tt>

<pre>

────────────────unsorted item list────────────────