Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
(Omissions of several language solutions.) |
(Scala contribution added.) |
||
Line 158: | Line 158: | ||
=={{header|GNU APL}}== |
=={{header|GNU APL}}== |
||
{{output?| |
{{output?|APL|reason}} |
||
<lang APL>⍝ Data |
<lang APL>⍝ Data |
||
Items←'beef' 'pork' 'ham' 'greaves' 'flitch' 'brawn' 'welt' 'salami' 'sausage' |
Items←'beef' 'pork' 'ham' 'greaves' 'flitch' 'brawn' 'welt' 'salami' 'sausage' |
||
Line 3,136: | Line 3,136: | ||
Output: |
Output: |
||
<pre> |
<pre>TotalValue |
||
TotalValue |
|||
349.38 |
349.38 |
||
Line 3,145: | Line 3,144: | ||
ham 3.6 |
ham 3.6 |
||
salami 3.0 |
salami 3.0 |
||
welt 3.5 |
welt 3.5 </pre> |
||
=={{header|Scala}}== |
|||
</pre> |
|||
===Functional approach (Tail recursive)=== |
|||
<lang Scala>import scala.annotation.tailrec |
|||
object ContinousKnapsackForRobber extends App { |
|||
val MaxWeight = 15.0 |
|||
val items = Seq( |
|||
Item("Beef", 3.8, 3600), |
|||
Item("Pork", 5.4, 4300), |
|||
Item("Ham", 3.6, 9000), |
|||
Item("Greaves", 2.4, 4500), |
|||
Item("Flitch", 4.0, 3000), |
|||
Item("Brawn", 2.5, 5600), |
|||
Item("Welt", 3.7, 6700), |
|||
Item("Salami", 3.0, 9500), |
|||
Item("Sausage", 5.9, 9800)) |
|||
// sort items by value per unit weight in descending order |
|||
def sortedItems = items.sortBy(it => -it.value / it.weight) |
|||
@tailrec |
|||
def packer(notPacked: Seq[Item], packed: Lootsack): Lootsack = { |
|||
if (!packed.isNotFull || notPacked.isEmpty) packed |
|||
else { |
|||
val try2fit = packed.copy(bagged = notPacked.head +: packed.bagged) |
|||
if (try2fit.isNotFull) packer(notPacked.tail, try2fit) |
|||
else { |
|||
try2fit.copy(lastPiece = packed.weightLeft / notPacked.head.weight) |
|||
} |
|||
} |
|||
} |
|||
case class Item(name: String, weight: Double, value: Int) |
|||
case class Lootsack(bagged: Seq[Item], lastPiece: Double = 1.0) { |
|||
private val totWeight = if (bagged.isEmpty) 0.0 |
|||
else bagged.tail.map(_.weight).sum + bagged.head.weight * lastPiece |
|||
def isNotFull: Boolean = weightLeft > 0 |
|||
def weightLeft: Double = MaxWeight - totWeight |
|||
override def toString = f"${show(bagged, lastPiece)}Totals: weight: $totWeight%4.1f, value: $totValue%6.2f" |
|||
private def totValue: BigDecimal = if (bagged.isEmpty) 0.0 |
|||
else (bagged.tail.map(_.value).sum + bagged.head.value * lastPiece) / 100 |
|||
private def show(is: Seq[Item], percentage: Double) = { |
|||
def toStr(is: Seq[Item], percentage: Double = 1): String = |
|||
is.map(it => f"${percentage * 100}%6.2f%% ${it.name}%-7s ${ |
|||
it.weight * percentage}%4.1f ${it.value * percentage / 100}%6.2f\n").mkString |
|||
toStr(is.tail.reverse) + toStr(Seq(is.head), percentage) |
|||
} |
|||
} |
|||
println(packer(sortedItems, Lootsack(Nil))) |
|||
}</lang> |
|||
{{Out}} |
|||
<pre>100.00% Salami 3.0 95.00 |
|||
100.00% Ham 3.6 90.00 |
|||
100.00% Brawn 2.5 56.00 |
|||
100.00% Greaves 2.4 45.00 |
|||
94.59% Welt 3.5 63.38 |
|||
Totals: weight: 15.0, value: 349.38</pre> |
|||
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/RHZQ4Xj/1 ScalaFiddle (JavaScript)] <!--or by [https://scastie.scala-lang.org/mDoBS77YSG2Z7w5xdAPzcw Scastie (JVM)]-->. |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |