Knapsack problem/Continuous: Difference between revisions

Content added Content deleted
m (→‎version 1: changed comment about sort method.)
m (→‎version 1: removed generic width calculations and used the title word lengths.)
Line 1,932: Line 1,932:
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
if maxW=='' | maxW==',' then maxW=15 /*burglar's knapsack max weight. */
if ddig=='' | ddig==',' then ddig= 2 /*# of decimal digits in FORMAT. */
if ddig=='' | ddig==',' then ddig= 2 /*# of decimal digits in FORMAT. */
wL=length('weight'); nL=length('total weight'); vL=length(' value ')
wL=length(' weight '); nL=length('total weight'); vL=length(' value ')
totW=0; totV=0
totW=0; totV=0
do j=1 while @.j\==''; parse var @.j n.j w.j v.j .
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.*/
end /*j*/ /* [↑] assign to separate lists.*/
items=j-1 /*ITEMS: the # of items in @ list*/
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*/
call show 'unsorted item list' /*display a header and the @ list*/
/* [↓] sort is OK for short lists*/
/* [↓] sort is OK for short lists*/
do sorts=2 to items /*sort by desending value/unit wt*/
do sorts=2 to items /*sort: descending value/unit wt.*/
_n=n.sorts; _w=w.sorts; _v=v.sorts /*calc. placeholders for DO loop.*/
_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*/
do k=sorts-1 by -1 to 1 while v.k/w.k < _v/_w /*order it*/
Line 1,955: Line 1,948:


call hdr "burglar's knapsack contents"
call hdr "burglar's knapsack contents"
do j=1 for items while totW < maxW; f=1
do j=1 for items while totW < maxW; f=1
if totW+w.j>=maxW then f=(maxW-totW)/w.j
if totW+w.j>=maxW then f=(maxW-totW)/w.j
totW=totW+w.j*f; totV=totV+v.j*f
totW=totW+w.j*f; totV=totV+v.j*f
call syf n.j, w.j*f, v.j*f
call syf n.j, w.j*f, v.j*f
end /*j*/
end /*j*/
call sep
call sep
call sy left('total weight',nL,'─'), format(totW,,ddig)
call sy left('total weight',nL,'─'), format(totW,,ddig)
Line 1,975: Line 1,968:
────────────────unsorted item list────────────────
────────────────unsorted item list────────────────


item weight value
item weight value
═══════════════ ══════ ═══════
════════════ ════════ ═══════
flitch 4.00 30.00
flitch 4.00 30.00
beef 3.80 36.00
beef 3.80 36.00
pork 5.40 43.00
pork 5.40 43.00
greaves 2.40 45.00
greaves 2.40 45.00
brawn 2.50 56.00
brawn 2.50 56.00
welt 3.70 67.00
welt 3.70 67.00
ham 3.60 90.00
ham 3.60 90.00
salami 3.00 95.00
salami 3.00 95.00
sausage 5.90 98.00
sausage 5.90 98.00




───────────burglar's knapsack contents────────────
───────────burglar's knapsack contents────────────


item weight value
item weight value
═══════════════ ══════ ═══════
════════════ ════════ ═══════
salami 3.00 95.00
salami 3.00 95.00
ham 3.60 90.00
ham 3.60 90.00
brawn 2.50 56.00
brawn 2.50 56.00
greaves 2.40 45.00
greaves 2.40 45.00
welt 3.50 63.38
welt 3.50 63.38
═══════════════ ══════ ═══════
════════════ ════════ ═══════
total weight─── 15.00
total weight 15.00
total value─── 349.38
total value 349.38
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"