Calculation of minimum sum using dynamic programming.

MinsumDP.scala

import scala.collection.mutable.ListBuffer

object MinsumDP extends App{
  def sum(ls: List[Int]) = ls.foldLeft(0)(_ + _)

  def buildOPT(OPT: Array[Array[Boolean]], A: Array[Int]): Unit ={
    for (
      i <- 1 until OPT.length;
      j <- 1 until OPT(0).length){

      OPT(i)(j) = OPT(i)(j-1)

      if(i >= A(j-1)){
        OPT(i)(j) = OPT(i)(j) || OPT(i-A(j-1))(j-1)
      }
    }
  }

  def getOPTPartition(OPT: Array[Array[Boolean]], A: Array[Int], min: Int): List[Int] = {
    val p1 = new ListBuffer[Int]
    val p2 = new ListBuffer[Int]

    var i = min
    var j = OPT(0).length -1

    while(i != 0){
      if(OPT(i)(j)){
        if((i >= A(j-1)) && OPT(i - A(j-1))(j-1)){
          p1 += A(j-1)
          i = i - A(j-1)
          j = j-1
        } else if(OPT(i)(j-1)) {
          p2 += A(j-1)
          i = i
          j = j-1
        }
      }
    }
    p1.toList
  }

  def printOPT(OPT: Array[Array[Boolean]]): Unit = {
    for (
      i <- 0 until OPT.length;
      j <- 0 until OPT(0).length) {
      print(OPT(i)(j) + " ")
      if (j == OPT(0).length - 1) println()
    }
    println()
  }

  def computePartition(numbers: List[Int]): Unit ={
    val pmax = numbers.sum/2
    val OPT: Array[Array[Boolean]] = Array.ofDim[Boolean](pmax+1, numbers.length+1)

    for(j <- 0 until numbers.length+1)
      OPT(0)(j) = true
    buildOPT(OPT, numbers.toArray)

    //printOPT(OPT)
    val min = (for(i <- pmax to 0 by -1 if (OPT(i)(numbers.length) == true)) yield i).head
    val  p1 = getOPTPartition(OPT, numbers.toArray, min)
    println(s"$numbers -- $p1 === ${numbers.sum -p1.sum*2}")
  }



  computePartition(List(3,1,1,2, 2,1))
  computePartition(List(1,5,3))
  computePartition(List(2,3,4,7,13))
  computePartition(List(1, 2, 2, 3, 4))
  computePartition(List(1, 2, 2, 3, 4,4,5,6,6,7,9))
  computePartition(List(1,5,11,5))
  computePartition(List(2,3,4,7,13))
  computePartition(List(1,5,10))

/**
 * OUTPUT:
 * List(3, 1, 1, 2, 2, 1) - List(1, 2, 2) === 0
 * List(1, 5, 3) - List(3, 1) === 1
 * List(2, 3, 4, 7, 13) - List(7, 4, 3) === 1
 * List(1, 2, 2, 3, 4) - List(4, 2) === 0
 * List(1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 9) - List(9, 7, 6, 2) === 1
 * List(1, 5, 11, 5) - List(5, 5, 1) === 0
 * List(2, 3, 4, 7, 13) - List(7, 4, 3) === 1
 */

}

Problem Definition:

Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?

Example 1:1 2 2 3 4
Answer : 0 (-1+2-2-3+4)

Example 2:2 3 4 7 13
Answer: 1 (+2-3-4-7+13)