Rosetta Code

Knapsack problem/Continuous: Difference between revisions

Page Discussion

Knapsack problem/Continuous (view source)

Revision as of 22:16, 23 September 2014

483 bytes removed ,  9 years ago
m
→‎version 1: removed generic width calculations and used the title word lengths.
m (→‎version 1: changed comment about sort method.)
m (→‎version 1: removed generic width calculations and used the title word lengths.)
Line 1,932:
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
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: the # of items in @ list*/
nL=nL + nL%4 /*nL: max length name + ≈ 25%.*/
wL=max(wL, length(format(totw,,ddig))) /*wL: max formatted weight width*/
vL=max(vL, length(format(totv,,ddig))) /*vL: " " value " */
totW=0; totV=0 /*set weight & value totals to 0.*/
call show 'unsorted item list' /*display a header and the @ list*/
/* [↓] sort is OK for short lists*/
do sorts=2 to items /*sort: by desendingdescending value/unit wt.*/
_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*/
Line 1,955 ⟶ 1,948:
 
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)
Line 1,975 ⟶ 1,968:
────────────────unsorted item list────────────────
 
item weight weight value
═══════════════════════════ ══════════════ ═══════
flitch 4.00 30.00
beef 3.80 36.00
pork 5.40 43.00
greaves 2.40 45.00
brawn 2.50 56.00
welt 3.70 67.00
ham 3.60 90.00
salami 3.00 95.00
sausage 5.90 98.00
 
 
───────────burglar's knapsack contents────────────
 
item weight weight value
═══════════════════════════ ══════════════ ═══════
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
═══════════════════════════ ══════════════ ═══════
total weight───weight 15.00
total value───value 349.38
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/141115"