Knapsack problem/Continuous: Difference between revisions

Line 2,801:

<br>Some amount of code was added to format the output better.

<lang rexx>/*REXX pgm solves the continuous burglar's knapsack problem; items with weight and value*/

@.= /*═══════ 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 arguments from the C.L. */

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

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

if d=='' | d=="," then d= 3 /*# decimal digits shown with FORMAT. */

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

wL=d+length('weight'); nL=d+length("total weight"); vL=d+length('value') /*lengths*/

⚫

totW=0; totV=0 /* [↓] assign item to separate lists. */

totW=0; totV=0

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

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

⚫

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

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

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

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

call sortD /*invoke descemdomg sort for: n. w. v.*/

call hdr "burglar's knapsack contents"

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

Line 2,826:

Line 2,824:

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

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

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

end /*j*/ /* [↑] display item, maybe with {all} */

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

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

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

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

Line 2,835:

Line 2,833:

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

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

end /*s*/

end /*s*/; return /* ↑↑↑ algorithm is OK for small arrays*/

return /* ↑↑↑ sort algorithm is OK for small arrays*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

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