Rosetta Code

Knapsack problem/Continuous: Difference between revisions

Page Discussion

Knapsack problem/Continuous (view source)

Revision as of 18:29, 23 September 2014

558 bytes added ,  9 years ago
m
→‎version 1: added comments, added a variable to specify number of decimal digits in the FORMAT for SAY, removed an unnecessary subroutine, allowed the specification of weight and output precision.
m (→‎version 2: ooRexx highlighting does (of course) not work within the lang section)
m (→‎version 1: added comments, added a variable to specify number of decimal digits in the FORMAT for SAY, removed an unnecessary subroutine, allowed the specification of weight and output precision.)
Line 1,916:
=={{header|REXX}}==
===version 1===
Any resemblenceresemblance to the Fortran code is 120% coincidental.
<lang rexx>/*REXX program solves 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 '
parse arg maxW ddig . /*get possible args from the C.L.*/
 
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
wL=length('weight'); nL=length('total weight'); vL=length(' value ')▼
if ddig=='' | ddig==',' then ddig= 2 /*# of decimal digits in FORMAT. */
▲wL=length('weight'); nL=length('total weight'); vL=length(' value ')
totW=0; totV=0
do j=1 while @.j\==''; parse var @.j n.j w.j v.j .
nL=max(nL, length(n.j)) /*ignore trailing blanks [↑] */
totW=totW+w.j
totV=totV+v.j
end /*j*/ /* [↑] assign to separate lists.*/
items=j-1 /*ITEMS is: the number # of items. in @ list*/
nL=nL + nL%4 /*nL: max length name + ≈ 25%.*/
wL=max(wL, length(format(totw,,2ddig))) /*wL: max formatted weight width*/
vL=max(vL, length(format(totv,,2ddig))) /*vL: max formatted" " value width " */
totW=0; totV=0 /*set weight & value totals to 0.*/
call show 'unsorted item list' /*display a header and the @ list*/
end /*for short lists, method is ok. */▼
 
do jsorts=2 to items /*sort by desending value/unit wt*/
k=j-1; _n=n.jsorts; _w=w.jsorts; _v=v.jsorts /*calc. placeholders for DO loop.*/
do k=ksorts-1 by -1 to 1 while v.k/w.k < _v/_w /*order it*/
kp1=k+1; n.kp1=n.k; w.kp1=w.k; v.kp1=v.k /*shuffle.*/
end /*k*/
kp1=k+1; n.kp1=_n; w.kp1=_w; v.kp1=_v
end /*jsorts*/
 
call hdr "burglerburglar's knapsack contents"
maxW=15 do j=1 for items while totW < /*burgler's knapsack max weight. */maxW
if do totW+w.j=1<maxW forthen items while totW < maxWdo
if totW=totW + w.j<maxW; then do totV=totV + v.j
call syf n.j, totW=totWw.j, + wv.j
totV=totV + v.jend
else call syf n.j, w.j, v.jdo
f=(maxW-totW) / endw.j
else do totW=totW + w.j*f; totV=totV + v.j*f
call syf n.j, w.j*f=(maxW-totW), / wv.j*f
totW=totW + w.j*fend
end totV=totV + v./*j*f/
call sep /* ddig = # callFORMAT syf n.j, w.j*f,decimal v.jdigits*f/
call sy left('total weight',nL,'─'), format(totW,,2ddig)▼
▲ end
call sy left('total value',nL,'─'), end /*j*/ , format(totV,,ddig)
call sep
▲call sy left('total weight',nL,'─'), format(totW,,2)
call sy left('total value',nL,'─'), , format(totV,,2)
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────one─liner subroutines────────────────────*/
hdr: indent=left('',9)say; call versesay center(arg(1),50,'─'); call titlesay; call septitle; 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 indentleft('',9) left(arg(1),nL) right(arg(2),wL) right(arg(3),vL); return
syf: call sy arg(1), format(arg(2),,2ddig), format(arg(3),,2ddig); return
title: call sy center('item',nL),center("weight",wL),center('value',vL); return</lang>
'''output''' using the default inputs of: &nbsp; <tt> 15 2 </tt>
verse: say; say center(arg(1),50,'─'); say; return</lang>
'''output'''
<pre style="height:50ex">
────────────────unsorted item list────────────────
Line 1,995 ⟶ 1,993:
 
 
───────────burgler───────────burglar's knapsack contents────────────
 
item weight value
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/141109"