Optymalna wartość bezwzględna sumy - szybki algorytm

Jest jakiś szybki algorytm, żeby znaleźć minimalną wartość takiej sumy:

dla odpowiednio za dużego , żeby można było sprawdzić każdą z możliwości.

Z góry dzięki!

Tak, wszystko z minusem - mniej nie będzie.

No tak, racja... :p zapomniałem modułu dopisać. Ta suma musi być najbliżej zera...

1. Sortujesz nie rosnąco.
2. Ustalasz sumę na zero.
3. Dla każdej liczby: jeżeli suma większa od zera to odejmujesz liczbę, w przeciwnym wypadku dodajesz.

Przeważnie tan algorytm da dosyć dobry wynik, ale nie ma gwarancji że najlepszy,

 
int min = 0;
Collections.sort(predkosci, Collections.reverseOrder());
for(Integer predkosc : predkosci) {
	min += (Math.abs(min - predkosc) < Math.abs(min + predkosc)) ? -predkosc : predkosc;
	min = Math.abs(min);
}

Dzięki... coś tu jest nie tak?

for(Integer predkosc : predkosci) min +=(min>0)?-predkosc:predkosc;

Pamiętaj że nie ma gwarancji że dostaniesz optymalną wartość.
Jakiego rzędu jest suma tych prędkości oraz ich liczebność?
Bo można dynamiczne programowanie zaadaptować.

Podoba mi się Twoje rozwiązanie, bo jest jeszcze prostsze. Na koniec trzeba wziąć tylko moduł z tego.

Danych nie jest dużo, ale mimo to coś robię źle.
Zadanie

Może ci się ten algorytm podoba tylko że zdecydowanie nie podoba się SPOJ'owi i słusznie.

A mniej więcej gdzie tkwi błąd w rozumowaniu?

8 7 5 5 5 - minimalny wynik 0, algorytm który podałem zwróci 4

Rzeczywiście... ale problem dobrze opisałem tym wzorem... Zobaczymy czy coś wymyślę :p

Do tego dynamiczne programowanie warto spróbować.

Moja propozycja :]

import scala.Array.ofDim
import scala.io.StdIn

object Main {
  def solve(a: Array[Int], start: Int, count: Int): Set[Int] = {
    if (count > 1) {
      val p1 = solve(a, start, count / 2)
      val p2 = solve(a, start + count / 2, count - count / 2)
      p1.flatMap(x1 => p2.flatMap(x2 => Set(x1 + x2, Math.abs(x1 - x2))))
    } else {
      assert(count == 1)
      Set(a(start))
    }
  }

  def main(args: Array[String]): Unit = {
    for (z <- 0 until StdIn.readInt()) {
      val n = StdIn.readInt()
      val a = ofDim[Int](n)
      for (i <- 0 until n) {
        a(i) = StdIn.readInt()
      }
      val min = solve(a, 0, a.length).min
      val max = a.sum
      println(s"$min $max")
    }
  }
}

Plus wersja niby trochę zoptymalizowana, ale dalej przekraczająca limit czasu:

import scala.Array.ofDim

object Main {
  val MaxSum = 10000
  val Threshold = 100

  def solveSmall(a: Array[Int], start: Int, count: Int): Set[Int] = {
    if (count > 1) {
      val p1 = solveSmall(a, start, count / 2)
      val p2 = solveSmall(a, start + count / 2, count - count / 2)
      p1.flatMap(x1 => p2.flatMap(x2 => Set(x1 + x2, Math.abs(x1 - x2))))
    } else {
      assert(count == 1)
      Set(a(start))
    }
  }

  def convert(s: Set[Int]): Array[Boolean] = {
    val a = ofDim[Boolean](s.max + 1)
    s.foreach(a(_) = true)
    a
  }

  def solveBig(a: Array[Int], start: Int, count: Int): Array[Boolean] = {
    val (p1, p2) = if (count > Threshold) {
      (solveBig(a, start, count / 2),
        solveBig(a, start + count / 2, count - count / 2))
    } else {
      (convert(solveSmall(a, start, count / 2)),
        convert(solveSmall(a, start + count / 2, count - count / 2)))
    }
    val r = ofDim[Boolean](Math.min(MaxSum + 1, p1.length + p2.length - 1))
    for (i <- p1.indices if p1(i); j <- p2.indices if p2(j)) {
      r(i + j) = true
      r(Math.abs(i - j)) = true
    }
    r
  }

  def solve(a: Array[Int]): Int = {
    if (a.length > Threshold) {
      solveBig(a, 0, a.length).indexWhere(identity)
    } else {
      solveSmall(a, 0, a.length).min
    }
  }

  def main(args: Array[String]): Unit = {
    for (z <- 0 until readInt()) {
      val n = readInt()
      val a = ofDim[Int](n)
      (0 until n).foreach(a(_) = readInt())
      val min = solve(a)
      val max = a.sum
      println(min + " " + max)
    }
  }
}

Niestety słabo rozumiem Twój pomysł.

Ale właśnie mi teraz zaakceptowało moje rozwiązanie.

Jego Idea jest taka...
Tworzę tablicę o wartościach boolean o rozmiarze równym maksymalnej sumie wszystkich prędkości dla danego przypadku + 1 (plus jeden żeby indeks mógł odpowiadać pewnej sumie).
Watość domyślną wartości tabelki ustawiam na false.
Dla pierwszej wczytywanej liczby ustawiam possible[pierwsza wczytana] na true.

Dla każdej kolejnej wczytanej liczby j, jeśli dla pewnego k possible[k] to true, ustawiam possible[Math.abs(k-j)] oraz possible[k+j] na true, a samo possible[k] na false, korzystając z tabelki pomocniczej.
Znajduję najmniejszy indeks dla którego possible[index] to true.

import java.io.*;
import java.util.*;

public class MainSPEED2 {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for(int t = Integer.parseInt(in.readLine().trim()); t > 0; t--) {
			int min = 0;
			int max = 0;
			int size = Integer.parseInt(in.readLine());
			int[] numbers = new int[size];
			
			for(int i = 0; i < size; i++) {
				numbers[i] = Integer.parseInt(in.readLine().trim());
				max += numbers[i];
			}
			
			boolean[] possible = new boolean[max+1];
			Arrays.fill(possible, false);
			possible[numbers[0]] = true;
			boolean[] temp = new boolean[max+1];
			
			for(int j = 1; j < size; j++) {
				Arrays.fill(temp, false);
				for(int k = 0; k <= max; k++) {
					if(possible[k]) {
						temp[k + numbers[j]] = true;
						temp[Math.abs(k - numbers[j])] = true;
					}
				}
				possible = temp.clone();
			}
			
			for(int i = 0; i <= max; i++) {
				if (possible[i]) {
					min = i;
					break;
				}
			}
			
			System.out.println(min + " " + max);
		}
	}
}

Skoro przeszło to spoko. Ja chyba trochę przekombinowałem :P A że nie mam dostępu do danych testowych to nie sprofiluję kodu na nich.