Anonymous user
Knapsack problem/Continuous: Difference between revisions
Scala contribution added.
(Omissions of several language solutions.) |
(Scala contribution added.) |
||
Line 158:
=={{header|GNU APL}}==
{{output?|
<lang APL>⍝ Data
Items←'beef' 'pork' 'ham' 'greaves' 'flitch' 'brawn' 'welt' 'salami' 'sausage'
Line 3,136:
Output:
<pre>TotalValue
349.38
Line 3,145 ⟶ 3,144:
ham 3.6
salami 3.0
welt 3.5 </pre>
=={{header|Scala}}==
===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}}==
{{trans|Perl}}
| |||