CODEWITHSUNDEEP
algorithmdynamic-programmingweighted-average
Artur
Artur

Reputation: 591

Minimize sum of weights such that weighted sum is zero

Given n <= 1000 integers 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 minimum S and for some specific S we can do dynamic programming by building dp(totalWeight, position, sum) but that would be too slow. How to solve it faster?

Upvotes: 3

Views: 723

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58241

Let's assume there's at least one positive and at least one negative weight (otherwise the problem has no solution). We know S is at most 2000, because if there's weights -c and +d, then d*-c + c*d = 0. And since c, d <= 1000, we know S (the minimum positive solution) is at most 2000. With 2000 weights, the maximum possible total is 2 million, and the minimum possible total is negative 2 million.

Now, we compute the minimum number of positive weights that can total 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 the solution, we find the minimum sum of the two arrays:

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

To speed things up, one can find a better bound for S (which reduces the N we need to consider). Let -c be the negative weight closest to 0, and d be the positive weight closest to 0, and e be the weight of largest magnitude. Then S <= c+d, so N can be reduced to (c+d)e. In fact, one 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 is bounded by min((d+c)/gcd(c, d) for -c a negative weight, and d a positive weight).

Putting all this together into a single Go solution, which you can run online 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 easy and some hard test cases. The code runs in under 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))
    }
}

Upvotes: 3

Related Questions