Math help or special calculator needed

[SvenBent]

MY wife is sitting with some math problems at work that i cant igive her an easy solutions for som im helping somebody here might know a fast way to caluclate this or could make a special calculator for it

The issues is she gets the info of a full paid amount but not what it is covering.
she have aprox 3 different prices to combine to get that full prices and have to figure out what it can be so she can put it in the system somehow correctly

if I'm not mistaken this is kinda like the traveling salesman thingy. anyway here is an real life example

Full paid price 30987
Unit 1 price 4537
Unit 2 price 5792
Unit 3 (no unit 3)


What combinations of units got sold to reach that price ?

Side info in case there a multiple answers the ones with the fewest units will always be correct.

[Piotr Tarsa]

Depending on the input restrictions a dynamic programming approach can give an answer in reasonable time. The requirement is a reasonably small universe of possible prices. Eg if possible prices are from 0.00 to 999.99 then there are 100000 different possible prices if the accuracy is to second digit after the point.

I don't see any correlation with TSP, though.

[SvenBent]

The solutions always need to be whole numbers as a unit cannot be divided so it can be 3.4 of unit1 and 2.2 of unit2 which kinda restrict it a bit

TSP is probably a far stretch. in this case it just a number of values that you need to add together to make an exact value. I was seeing TSP and every path as different values that had to be added together to reach the minimum distance (instead of an exact value) but there is more difference then that.

if possible prices are from 0.00 to 999.99 then there are 100000 different possible prices if the accuracy is to second digit after the point.
I'm not sure i follow the prices are given in each task so its the number of units that needs to be found that's the actual problem

[Matt Mahoney]

That's the subset sum problem, which is NP-complete. You can't do much better than a brute force search.

[Piotr Tarsa]

For me, the problem looks more like http://en.wikipedia.org/wiki/Knapsack_problem and it is solvable by dynamic programming.

I've coded a solution: http://ideone.com/1AzRnU
It does scale the prices by 100 and converts them to integers. It will fail if price isn't integral after scaling by 100.
Complexity is like O(price * scale factor * number of units).

Input:
<sum>
<unit1>
<unit2>
<unit3>

If some unit is not used, enter 0.

[nburns]

The general case sounds like subset sum, but if it's always three prices, it can be something like O(n^2) I think.

The connection to TSP would be that subset sum and TSP are both NP-hard.

[Piotr Tarsa]

The general case sounds like subset sum, but if it's always three prices, it can be something like O(n^2) I think.

O(n ^ 2) but what does 'n' mean here?

The connection to TSP would be that subset sum and TSP are both NP-hard.

Far fetched.

Sven:
More "real life" examples would be useful. My solution is here (ie in previous post) so testing it on another input is trivial.

[SvenBent]

Woot thank you Piotr. ehrm how do i make this into a program though?

I don't have any real life info at this point but i will get more.

[Piotr Tarsa]

Well, it is a program, reading from standard input and writing to standard output (ie a command line program), written in Scala. Running Scala programs can be problematic so I can rewrite it in eg Java.

[SvenBent]

If you could you get my blessing that would be so awesome and remove a lot of work stress for my wife

I tried downloading scala thing and use scalac. It just didnt do anything


I dont know if this help but their actually might be a max per units

see RL example it goes like this
a hospital bills an insurance for 5 days i type 1, 4 days of type2 and 12 days of type3
the insurance does not pay the full amount but only a certain but unknown numbers of days we do however know the amount paid
my wife now has to combine the prices of the 3 day types to adjust the bill so its fits the amount paid by the insurance

off cause the easiest solutions would be for the insurance to report what they did and did not pay for but yeah.. insurance companies

the amounts of different units is different from case to case
the pricing on the units is different from case to case
and the amount paid is different from case to case

The numbers of units bill'ed is different from case to case

[Piotr Tarsa]

Try doing:

scalac Main.scala
scala Main

Rename file before executing that.
It should then wait for the 4 numbers (1 for sum, 3 for units), separated by newlines.

I'm at work so I can't spend time on translating the program to Java now.

[SvenBent]

''"java"'' is not recognized as an internal or external command, operable program or batch file.

what i did was i went to "The Scala Programming Language" site www.scala-lang.org/
downloaded scala 2.11.2
installed the msi package
renamed you .scala file
scalac main.scala
and
scalac main

But just got the java issues message

[Bulat Ziganshin]

i think it's the Linear Diophantine equation

[Piotr Tarsa]

SvenBent:
You need Java runtime to run Java-based programs (I recommend disabling support for Java applets after install) and Scala is based on Java. Then you need to run 'scalac' to compile and 'scala' to run compiled program as I've outlined in previous post.

[SvenBent]

Ty again. I found out i needed to manually install java 8 and the batch file from scala "works" as in it start and does something,
Just weird that the java site want me to go down to java 7 v67 that i had before. or is this now 2 compete different things.

C:\Users\Admin\Desktop\Solver>scalac main.scala
warning: there were two deprecation warnings; re-run with -deprecation for detai
ls
one warning found

C:\Users\Admin\Desktop\Solver>scalac main.scala -deprecation
main.scala:4: warning: method readLine in class DeprecatedConsole is deprecated:
 Use the method in scala.io.StdIn
    val sum = BigDecimal(Console.readLine()).*(100).toIntExact
                                 ^
main.scala:5: warning: method readLine in class DeprecatedConsole is deprecated:
 Use the method in scala.io.StdIn
    val unitPrices = (0 until 3).map(_ => BigDecimal(Console.readLine()).*(100).
toIntExact).filter(_ != 0)
                                                             ^
two warnings found

[nburns]

i think it's the Linear Diophantine equation

This seems like the right way to look at it. In other words, the problem is to solve an equation such as

q_0*p_0 + q_1*p_1 + q_2*p_2 = P

for item quantities q_i, prices p_i, and total price P, with the constraint that all q_i must be integers and >= 0.

The wikipedia page has a lot of useful info on it. Knowing that Fermat's last theorem is somehow a relative of this problem doesn't exactly breed confidence.

[nburns]

O(n ^ 2) but what does 'n' mean here?

n would be the number of different prices that may individually be added or not to the total. That was based on a misreading of the problem, I think, because there seem to only be a small number of prices (e.g. n~3), but each can be added zero or more times. I was thinking it was similar to some other problem I had read about.

Far fetched.

The actual subset sum problem is NP-hard (look it up). This could degrade into subset sum, but then it would tend to not be worthwhile to solve.

Sven:
More "real life" examples would be useful. My solution is here (ie in previous post) so testing it on another input is trivial.

If I understand this right, it's a very practical kind of problem. It's like when when you learn the score in the middle of an American football game and try to deduce what combinations of field goals (3 pts) and touchdowns (7 pts) could have produced that score.*

*I simplified things here a bit.

[Piotr Tarsa]

Sven:
So, after all, it works or not? Deprecation warnings aren't particularly dangerous and they don't stop program from compiling (well, only errors stop). So you should be able to run the sequence I've posted in post #11.

Java site shows Java 7 because it turned out that Java 8 can cause compatibility problems (i.e. there are some widely used programs which aren't written in portable ways, compliant with specification of Java). But if it works, it's good.

Also, maybe pay attention to letter case. I don't know if it plays a significant role under Windows but it's better to be safe than sorry.

[nburns]

Stuff like this ought to be a good candidate for writing in JavaScript, since it hardly demands any resources and should be easy. I've made lots of runnable HTML files, but they can cause problems with IE. jsfiddle should work.

It would be nifty if this board let you post runnable scripts. I've never seen that feature on a forum, probably because it seems like a security risk. It wouldn't be if done right.

[Piotr Tarsa]

I've improved the code (hope no bugs introduced) so that it prompts user to enter numbers.

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:

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

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