Anonymous user
Knapsack problem/Continuous: Difference between revisions
→Tcl: Added implementation
m (language corrections) |
(→Tcl: Added implementation) |
||
Line 306:
TOTAL WEIGHT: 15.00
TOTAL VALUE: 349.38</pre>
=={{header|Tcl}}==
<lang tcl>package require Tcl 8.5
# Uses the trivial greedy algorithm
proc continuousKnapsack {items massLimit} {
# Add in the unit prices
set idx -1
foreach item $items {
lassign $item name mass value
lappend item [expr {$value / $mass}]
lset items [incr idx] $item
}
# Sort by unit prices
set items [lsort -decreasing -real -index 3 $items]
# Add items, using most valuable-per-unit first
set result {}
set total 0.0
set totalValue 0
foreach item $items {
lassign $item name mass value unit
if {$total + $mass < $massLimit} {
lappend result [list $name $mass $value]
set total [expr {$total + $mass}]
set totalValue [expr {$totalValue + $value}]
} else {
set mass [expr {$massLimit - $total}]
set value [expr {$unit * $mass}]
lappend result [list $name $mass $value]
set totalValue [expr {$totalValue + $value}]
break
}
}
# We return the total value too, purely for convenience
return [list $result $totalValue]
}</lang>
Driver for this particular problem:
<lang tcl>set items {
{beef 3.8 36}
{pork 5.4 43}
{ham 3.6 90}
{greaves 2.4 45}
{flitch 4.0 30}
{brawn 2.5 56}
{welt 3.7 67}
{salami 3.0 95}
{sausage 5.9 98}
}
lassign [continuousKnapsack $items 15.0] contents totalValue
puts [format "total value of knapsack: %.2f" $totalValue]
puts "contents:"
foreach item $contents {
lassign $item name mass value
puts [format "\t%.1fkg of %s, value %.2f" $mass $name $value]
}</lang>
Output:
<pre>
total value of knapsack: 349.38
contents:
3.0kg of salami, value 95.00
3.6kg of ham, value 90.00
2.5kg of brawn, value 56.00
2.4kg of greaves, value 45.00
3.5kg of welt, value 63.38
</pre>
| |||