Rosetta Code

Knapsack problem/Continuous: Difference between revisions

Page Discussion

Knapsack problem/Continuous (view source)

Revision as of 19:06, 24 September 2014

614 bytes added ,  9 years ago
→‎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.
(→‎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:
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 (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 ddigd . /*get possible args from the C.L.*/
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
if ddig d=='' | ddig d==',' then ddig d= 23 /*# of decimal digits in FORMAT. */
wL=d+length(' weight '); nL=d+length('total weight'); vL=d+length(' value ')
totW=0; totV=0
do j#=1 while @.j#\==''; parse var @.j# n.j# w.j# v.j# .
end /*j#*/ /* [↑] assign to separate lists.*/
items#=j#-1 /*ITEMS#: the # number of items in @ list.*/
call show 'unsorted item list' /*display a header and the @ list.*/
call sortD /*invoke [↓]using sorta isdescending OK for short listssort.*/
call hdr "burglar's knapsack contents"▼
do sorts=2 to items /*sort: descending value/unit wt.*/
do j=1 for items# while totW < maxW; f=1 f=1/*grab items*/▼
_n=n.sorts; _w=w.sorts; _v=v.sorts /*calc. placeholders for DO loop.*/
do k=sorts-1 by -1 toif 1totW+w.j>=maxW whilethen v.kf=(maxW-totW)/w.k < _v/_wj /*ordercalc itfract*/
kp=k+1; n.kptotW=ntotW+w.kj*f; w.kp=w.k; v.kptotV=totV+v.kj*f /*shuffle.add──►tots*/
call syf left(word('{all}',1+(f\==1)),5) n.j, w.j*f, v.j*f▼
end /*k*/▼
end /*j*/ end /*j↑show item*/▼
kp=k+1; n.kp=_n; w.kp=_w; v.kp=_v▼
call sep; say end /*sorts [↓] $ supresses trailing Θs.*/
call sy left('total weight',nL,'─'), $(format(totW,,ddigd))▼
 
call sy left('total value',nL,'─'), , , $(format(totV,,ddigd))▼
▲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.*/
/*──────────────────────────────────one─liner subroutines────────────────────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 items#; call syf n.j,w.j,v.j; end; say; 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),,ddigd)), $(format(arg(3),,ddigd)); return
title: call sy center('item',nL), center("weight",wL), center('value',vL); return</lang>
$: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*/
▲ kp a=k+1; n.kpa=_n; w.kpa=_w; v.kpa=_v /*place item. */
▲ end end /*ksort*/
return /* ↑ ↑ ↑ algorithm is OK for smallish arrays.*/</lang>
▲'''output''' using the default inputs of: &nbsp; <tt> 15 23 </tt>
<pre>
────────────────unsorted item list────────────────
 
item weight value
═══════════════ ═════════ ════════
════════════ ════════ ═══════
flitch 4.00 30.00
beef 3.808 36.00
pork 5.404 43.00
greaves 2.404 45.00
brawn 2.505 56.00
welt 3.707 67.00
ham 3.606 90.00
salami 3.00 95.00
sausage 5.909 98.00
 
 
───────────burglar's knapsack contents────────────
 
item weight value
═══════════════ ═════════ ════════
════════════ ════════ ═══════
{all} salami 3 3.00 95.00
{all} ham 3.6 3.60 90.00
{all} brawn 2.5 2.50 56.00
{all} greaves 2.4 2.40 45.00
welt welt 3.505 63.38378
═══════════════ ═════════ ════════
════════════ ════════ ═══════
 
total weight 15.00
total weight─── value 349.3815
total value─── 349.378
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/141117"