最小化权重总和，使加权总和为零

Question

给定 n <= 1000 个整数 x(1), x(2), ..., x(n)，其中 |x(i)| <= 1000。我们想为每个元素分配非负整数权重 c(1), c(2), ..., c(n)，使得 c(1) * x(1) + ... + c(n) * x(n) = 0。让S = c(1) + ... + c(n)。我们需要 S > 0 并且我们希望最小化 S。

我们可以对最小值 S 进行二进制搜索，对于某些特定的 S 我们可以通过构建 dp(totalWeight, position, sum) 来进行动态规划，但那会太慢。如何更快解决？

Answer 1

让我们假设至少有一个正权重和至少一个负权重（否则问题无解）。我们知道 S 最多为 2000，因为如果有权重 -c 和 +d，则 d*-c + c*d = 0。并且由于 c, d <= 1000，我们知道 S（最小正解）位于最多2000个。2000个权重，最大可能总数为200万，最小可能总数为负200万。

现在，我们计算总和为 0 到 200 万的最小正权重数。

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

我们对负权重做同样的事情：

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

为了找到解决方案，我们找到两个数组的最小总和：

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

为了加快速度，可以为 S 找到更好的界限（这减少了我们需要考虑的 N）。设 -c 是最接近 0 的负权重，d 是最接近 0 的正权重，e 是最大幅度的权重。那么S <= c+d，所以N可以化简为(c+d)e。事实上，可以做得更好一点：如果 -c 和 d 是任意两个 negative/positive 权重，那么 d/gcd(c, d) * -c + c/gcd(c, d) * d = 0，所以 S 受 min((d+c)/gcd(c, d) 的限制，因为 -c 是负权重，d 是正权重）。

将所有这些放在一个单一的 Go 解决方案中，您可以在此处运行在线：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
}

并测试一些简单的和一些困难的测试用例。在我的笔记本电脑上，代码运行不到半秒。

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))
    }
}

最小化权重总和，使加权总和为零

Minimize sum of weights such that weighted sum is zero

algorithm

dynamic-programming

weighted-average