Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
m (language corrections) |
(→Tcl: Added implementation) |
||
Line 306: | Line 306: | ||
TOTAL WEIGHT: 15.00 |
TOTAL WEIGHT: 15.00 |
||
TOTAL VALUE: 349.38</pre> |
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> |