Lösen von linearen Gleichungen

Question

Ich muss die Integrallösung einer Gleichung ax+by=c so herausfinden, dass x>=0 und y>=0 und Wert von (x+y) is minimum.

Ich weiß, wenn c%gcd(a,b)}==0 dann ist es immer möglich. Wie finde ich die Werte von x und y?

Mein Ansatz

for(i 0 to 2*c): 
    x=i 
    y= (c-a*i)/b 
    if(y is integer) 
    ans = min(ans,x+y) 

Gibt es einen besseren Weg, dies zu tun? Bessere Zeit Komplexität.

Answer 1

Zuerst nehmen wir an a,b,c>0 so:

a.x+b.y = c 
x+y = min(xi+yi) 
x,y >= 0 
a,b,c > 0 
------------------------ 
x = (c - b.y)/a 
y = (c - a.x)/b 
c - a.x >= 0 
c - b.y >= 0 
c >= b.y 
c >= a.x 
x <= c/x 
y <= c/b 

So naiv O(n) Lösung in C++ wie folgt aus:

void compute0(int &x,int &y,int a,int b,int c) // naive 
    { 
    int xx,yy; 
    xx=-1; yy=-1; 
    for (y=0;;y++) 
     { 
     x = c - b*y; 
     if (x<0) break;  // y out of range stop 
     if (x%a) continue; // non integer solution 
     x/=a;    // remember minimal solution 
     if ((xx<0)||(x+y<=xx+yy)) { xx=x; yy=y; } 
     } 
    x=xx; y=yy; 
    } 

, wenn keine Lösung es gibt -1,-1 gefunden Wenn Sie über die Gleichung a denken Bit dann sollten Sie erkennen, dass die minimale Lösung wird, wenn x oder y minimal ist (die davon abhängt a<b condition), also können wir durch Hinzufügen solcher Heuristiken nur die minimale Koordinate erhöhen, bis die erste Lösung gefunden wurde. Dies wird erheblich beschleunigt die ganze Sache:

void compute1(int &x,int &y,int a,int b,int c) 
    { 
    if (a<=b){ for (x=0,y=c;y>=0;x++,y-=a) if (y%b==0) { y/=b; return; } } 
    else  { for (y=0,x=c;x>=0;y++,x-=b) if (x%a==0) { x/=a; return; } } 
    x=-1; y=-1; 
    } 

ich diese auf meinem Setup gemessen:

     x  y  ax+by  x+y  a=50 b=105 c=500000000 
[ 55.910 ms]  10 4761900 500000000 4761910 naive 
[ 0.000 ms]  10 4761900 500000000 4761910 opt 
         x  y  ax+by  x+y  a=105 b=50 c=500000000 
[ 99.214 ms] 4761900  10 500000000 4761910 naive 
[ 0.000 ms] 4761900  10 500000000 4761910 opt 

Der ~2.0x Unterschied für naive Methode Zeiten ist aufgrund a/b=~2.0 und Auswahl schlechter koordinieren iterieren in der zweite Lauf.

Jetzt behandeln nur Sonderfälle, wenn a,b,c Null ... es

Answer 2

die Extended Euclidean Algorithm Verwendung und die Theorie der linear Diophantine equations (Division durch Null zu vermeiden) ist nicht erforderlich, zu suchen. Hier ist eine Python 3-Implementierung:

def egcd(a,b): 
    s,t = 1,0 #coefficients to express current a in terms of original a,b 
    x,y = 0,1 #coefficients to express current b in terms of original a,b 
    q,r = divmod(a,b) 
    while(r > 0): 
     a,b = b,r 
     old_x, old_y = x,y 
     x,y = s - q*x, t - q*y 
     s,t = old_x, old_y 
     q,r = divmod(a,b) 
    return b, x ,y 

def smallestSolution(a,b,c): 
    d,x,y = egcd(a,b) 
    if c%d != 0: 
     return "No integer solutions" 
    else: 
     u = a//d #integer division 
     v = b//d 
     w = c//d 
     x = w*x 
     y = w*y 
     k1 = -x//v if -x % v == 0 else 1 + -x//v #k1 = ceiling(-x/v) 
     x1 = x + k1*v # x + k1*v is solution with smallest x >= 0 
     y1 = y - k1*u 
     if y1 < 0: 
      return "No nonnegative integer solutions" 
     else: 
      k2 = y//u #floor division 
      x2 = x + k2*v #y-k2*u is solution with smallest y >= 0 
      y2 = y - k2*u 
      if x2 < 0 or x1+y1 < x2+y2: 
       return (x1,y1) 
      else: 
       return (x2,y2) 

Typischer Lauf:

>>> smallestSolution(1001,2743,160485) 
(111, 18) 

Die Art und Weise funktioniert es: zuerst den erweiterten euklidischen Algorithmus verwendet d = gcd(a,b) und eine Lösung zu finden, (x,y). Alle anderen Lösungen haben die Form (x+k*v,y-k*u), wobei u = a/d und v = b/d. Da x+y linear ist, hat es keine kritischen Punkte und wird daher im ersten Quadranten minimiert, wenn entweder x so klein wie möglich ist oder y so klein wie möglich ist. Die obige k ist ein beliebiger ganzzahliger Parameter. Durch entsprechende Verwendung von floor und ceiling können Sie die Integer-Punkte entweder mit x so klein wie möglich oder y ist so klein wie möglich. Nimm einfach den mit der kleinsten Summe.

Zum Bearbeiten klicken: Mein ursprünglicher Code verwendet die Python-Funktion math.ceiling an -x/v angewendet.Dies ist bei sehr großen Ganzzahlen problematisch. Ich habe es optimiert, so dass die Decke mit nur Int-Operationen berechnet wird. Es kann nun beliebig große Zahlen verarbeiten:

>>> a = 236317407839490590865554550063 
>>> b = 127372335361192567404918884983 
>>> c = 475864993503739844164597027155993229496457605245403456517677648564321 
>>> smallestSolution(a,b,c) 
(2013668810262278187384582192404963131387, 120334243940259443613787580180) 
>>> x,y = _ 
>>> a*x+b*y 
475864993503739844164597027155993229496457605245403456517677648564321 

Die meisten der Berechnung erfolgt in der erweiterten euklidischen Algorithmus ausgeführt wird, die O(min(a,b)) zu sein, ist bekannt.