भार का योग कम से कम करें जैसे कि भारित योग शून्य है - एल्गोरिथम, डायनेमिक-प्रोग्रामिंग, भारित-औसत

दिया हुआ 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) लेकिन यह बहुत धीमा होगा। इसे तेजी से कैसे हल करें?

उत्तर:

कम से कम एक सकारात्मक और पर "मान लेते हैं"कम से कम एक नकारात्मक वजन (अन्यथा समस्या का कोई हल नहीं है)। हम जानते हैं कि S अधिकतम 2000 पर है, क्योंकि यदि वहाँ वजन -c और + d है, तो d * -c + c * d = 0. और c, d <= 1000 से, हम S (न्यूनतम सकारात्मक समाधान) जानते हैं अधिकतम 2000 पर है। 2000 वज़न के साथ, अधिकतम संभव कुल 2 मिलियन है, और न्यूनतम संभव कुल नकारात्मक 2 मिलियन है।

अब, हम सकारात्मक वज़न की न्यूनतम संख्या की गणना करते हैं जो कि 0 से 2 मिलियन तक हो सकती है।

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 हमें विचार करने की आवश्यकता है)।आज्ञा देना-ऋणात्मक वजन 0 के निकटतम होना चाहिए, और धनात्मक भार 0 के निकटतम होना चाहिए, और सबसे बड़े परिमाण का वजन होना चाहिए। फिर S <= c + d, इसलिए N को (c + d) e तक घटाया जा सकता है। वास्तव में, कोई थोड़ा बेहतर कर सकता है: यदि -सी और डी किसी भी दो नकारात्मक / सकारात्मक भार हैं, तो d / gcd (c, d) * -c + c / gcd (c, d) * d = 0, so S, min ((d + c) / gcd (c, d) -ca ऋणात्मक भार और दा धनात्मक भार) से घिरा है।

यह सब एक साथ एक एकल समाधान में लाना, जिसे आप यहां ऑनलाइन चला सकते हैं: 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))
}
}