Zminimalizuj sumę wag tak, aby suma ważona była zerowa - algorytm, programowanie dynamiczne, średnia ważona

Dany n <= 1000 liczby całkowite x(1), x(2), ..., x(n) gdzie |x(i)| <= 1000. Chcemy przypisać nieujemny liczby całkowite c(1), c(2), ..., c(n) do każdego elementu takiego, że c(1) * x(1) + ... + c(n) * x(n) = 0. Pozwolić S = c(1) + ... + c(n). Potrzebujemy S > 0 i chcemy zminimalizować S.

Możemy wyszukiwać binarnie minimum S i dla niektórych konkretnych S możemy robić dynamiczne programowanie przez budowanie dp(totalWeight, position, sum) ale to byłoby zbyt wolne. Jak rozwiązać to szybciej?

Odpowiedzi:

Załóżmy, że istnieje co najmniej jeden pozytywny i atnajmniej jedna ujemna waga (inaczej problem nie ma rozwiązania). Wiemy, że S wynosi co najwyżej 2000, ponieważ jeśli istnieją wagi -c i + d, to d * -c + c * d = 0. A ponieważ c, d <= 1000, znamy S (minimalne pozytywne rozwiązanie) wynosi co najwyżej 2000. Przy masach 2000 maksymalna możliwa suma wynosi 2 miliony, a minimalna możliwa suma wynosi minus 2 miliony.

Teraz obliczamy minimalną liczbę dodatnich wag, które mogą wynosić od 0 do 2 milionów.

N = 2000000
p = [0] + [infinity] * N
for w in positive weights:
for i = w ... N:
p[i] = min(p[i], p[i-w]+1)

Robimy to samo dla ujemnych wag:

n = [0] + [infinity] * N
for w in negative weights:
for i = -w ... N:
n[i] = min(n[i], n[i+w]+1)

Aby znaleźć rozwiązanie, znajdujemy minimalną sumę dwóch tablic:

S = infinity
for i = 1 ... N:
S = min(S, n[i] + p[i])

Aby przyspieszyć, można znaleźć lepszą oprawę S (co zmniejsza N musimy wziąć pod uwagę). Niech -c będzie ujemną wagą najbliższą 0, d będzie dodatnią wagą najbliższą 0, a e będzie wagą największej wielkości. Wtedy S <= c + d, więc N można zredukować do (c + d) e. W rzeczywistości można zrobić trochę lepiej: jeśli -c i d są dowolnymi dwoma ujemnymi / dodatnimi wagami, to d / gcd (c, d) * -c + c / gcd (c, d) * d = 0, więc S jest ograniczony przez min ((d + c) / gcd (c, d) dla ujemnej masy i ujemnej wagi).

Łącząc to wszystko w jedno rozwiązanie Go, które można uruchomić online tutaj: https://play.golang.org/p/CAa54pQs26

package main

import "fmt"

func boundS(ws []int) int {
best := 5000
for _, pw := range ws {
if pw < 0 {
continue
}
for _, nw := range ws {
if nw > 0 {
continue
}
best = min(best, (pw-nw)/gcd(pw, -nw))
}
}
return best
}

func minSum(ws []int) int {
maxw := 0
for _, w := range ws {
maxw = max(maxw, abs(w))
}
N := maxw * boundS(ws)
n := make([]int, N+1)
p := make([]int, N+1)
for i := 1; i <= N; i++ {
n[i] = 5000
p[i] = 5000
}
for _, w := range ws {
for i := abs(w); i <= N; i++ {
if w > 0 {
p[i] = min(p[i], 1+p[i-w])
} else {
n[i] = min(n[i], 1+n[i+w])
}
}
}
S := p[1] + n[1]
for i := 1; i <= N; i++ {
S = min(S, p[i]+n[i])
}
return S
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func abs(a int) int {
if a < 0 {
return -a
}
return a
}

func gcd(a, b int) int {
if a < b {
a, b = b, a
}
for b > 0 {
a, b = b, a%b
}
return a
}

I testowanie na kilku łatwych i kilku trudnych testach. Kod działa na mniej niż pół sekundy na moim laptopie.

func isPrime(p int) bool {
if p < 4 {
return p >= 2
}
for i := 2; i*i <= p; i++ {
if p%i == 0 {
return false
}
}
return true
}

func main() {
var middle, ends, altPrimes []int
sign := 1
for i := -1000; i <= 1000; i++ {
if i == 0 {
continue
}
if abs(i) <= 500 {
middle = append(middle, i)
} else {
ends = append(ends, i)
}
if abs(i) >= 500 && isPrime(i) {
altPrimes = append(altPrimes, sign*i)
sign *= -1
}
}
cases := [][]int{
[]int{999, -998},
[]int{10, -11, 15, -3},
middle,
ends,
altPrimes,
}
for i, ws := range cases {
fmt.Println("case", i+1, minSum(ws))
}
}