Minimize the sum of the weights so that the weighted sum is zero
Integers n <= 1000
are given x(1), x(2), ..., x(n)
, where |x(i)| <= 1000
. We want to assign non-negative integer weights c(1), c(2), ..., c(n)
to each element such that c(1) * x(1) + ... + c(n) * x(n) = 0
. Let S = c(1) + ... + c(n)
. We need S > 0
and we want to minimize S
.
We can binary search for the minimum S
, and for some specific ones S
we can do dynamic programming by creating dp(totalWeight, position, sum)
, but it will be too slow. How to solve this problem faster?
source to share
Suppose there is at least one positive and at least one negative weight (otherwise the problem has no solution). We know that S is at most 2000, because if there are weights -c and + d, then d * -c + c * d = 0. And since c, d <= 1000, we know S (minimum positive decision) no more than 2000. With 2000 weight, the maximum possible total number is 2 million, and the minimum possible total number of negative ones is 2 million.
We will now calculate the minimum number of positive weights that can range from 0 to 2 million.
N = 2000000 p = [0] + [infinity] * N for w in positive weights: for i = w ... N: p[i] = min(p[i], p[i-w]+1)
We do the same for negative weights:
n = [0] + [infinity] * N
for w in negative weights:
for i = -w ... N:
n[i] = min(n[i], n[i+w]+1)
And to find a solution, we will find the minimum sum of two arrays:
S = infinity
for i = 1 ... N:
S = min(S, n[i] + p[i])
To speed S
things up, a better estimate can be found for (which decreases N
, which we need to consider). Let -c be the negative weight closest to 0, d be the positive weight closest to 0, e the weight of the largest value. Then S <= c + d, so N can be reduced to (c + d) e. In fact, we can do a little better: if -c and d are any two negative / positive weights, then d / gcd (c, d) * -c + c / gcd (c, d) * d = 0, so S bounded by min ((d + c) / gcd (c, d) for negative weight and yes positive weight).
Putting it all together into one Go solution that you can run here: 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
}
And testing on some simple and complex tests. The code runs in less than half a second on my laptop.
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))
}
}
source to share