I've improved the code (hope no bugs introduced) so that it prompts user to enter numbers.
Code:
import scala.io.StdIn
object Main {
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println("Enter sum (followed by newline)")
val sum = BigDecimal(StdIn.readLine()).*(100).toIntExact
println("Enter three units (each followed by newline; enter 0 for unused unit)")
val unitPrices = (0 until 3).map(_ => BigDecimal(StdIn.readLine()).*(100).toIntExact).filter(_ != 0)
val pricesGcd = if (unitPrices.isEmpty) 0 else unitPrices.reduce(gcd)
val unitPricesReduced = unitPrices.map(_ / pricesGcd)
val dynArray = Array.ofDim[Int](sum / pricesGcd + 1, unitPrices.length)
dynArray.foreach(row => row.indices.foreach(row(_) = -1))
dynArray(0) = Array.fill[Int](unitPrices.length)(0)
for ((row, rowIndex) <- dynArray.zipWithIndex;
elemIndex <- row.indices) {
val unitPrice = unitPricesReduced(elemIndex)
if (rowIndex >= unitPrice) {
val upperElem = dynArray(rowIndex - unitPrice)(elemIndex)
if (upperElem >= 0) {
row(elemIndex) = upperElem + 1
}
}
if (elemIndex > 0) {
val leftElem = row(elemIndex - 1)
if (row(elemIndex) < 0 || (leftElem >= 0 && leftElem <= row(elemIndex))) {
row(elemIndex) = leftElem
}
}
}
val counts = (0 until unitPrices.length).map(_ => 0).toArray
var col = unitPrices.length - 1
var row = sum / pricesGcd
while (row > 0 && dynArray(row)(col) >= 0) {
val elem = dynArray(row)(col)
if (col > 0 && elem == dynArray(row)(col - 1)) {
col -= 1
} else if (row >= unitPricesReduced(col) && elem == dynArray(row - unitPricesReduced(col))(col) + 1) {
counts(col) += 1
row -= unitPricesReduced(col)
} else {
throw new Error
}
}
if (dynArray(row)(col) >= 0) {
print(f"${sum / 100.0}%1.2f = ")
println(counts.zipWithIndex.map {
case (count, index) => f"$count%d * ${unitPrices(index) / 100.0}%1.2f"
}.mkString(" + "))
println(if (sum == counts.zip(unitPrices).map{case (a, b) => a * b}.sum) "sum correct" else "sum incorrect")
} else {
println("No solution")
}
}
}
Save at Main.scala and run as described in post #11.
Sample output:
Code:
Enter sum (followed by newline)
342.25
Enter three units (each followed by newline; enter 0 for unused unit)
32.01
0.01
64
342,25 = 0 * 64,00 + 10 * 32,01 + 2215 * 0,01
sum correct
Code:
Enter sum (followed by newline)
35.23
Enter three units (each followed by newline; enter 0 for unused unit)
53.53
3.53
22.2
No solution