¿Cómo encontrar un par de soluciones de la ecuación diofantina lineal tal que minimice esta expresión?

Question

Este es un típico problema de codificación matemática que encontré aquí Problema .
Así que déjame que te lo explique
Suponga que tiene dos valores $a$ y $b$ y para seleccionar este valor $a$ una vez que te lleva $c_1$ costo y se necesita $c_2$ valor de coste de uso $b$ .
Debes resolver esta ecuación para $(x,y)$
$ax$ + $by$ = $N$ donde $N$ es un valor que se le da
Encontrar tal $(x,y)$ que minimice esta expresión $x*c_1 + y*c_2$ .
o informar si no es posible resolver

Es una ecuación lineal diofantina clara y puedo resolver fácilmente $(x,y)$ utilizando el GCD extendido Pero no sé cómo hacerlo minimizando la expresión dada.
Un ejemplo para esta pregunta es suponer que tienes $a=3$ $b=4$ y $c_1 = 1$ y $c_2=2$ y $N=43$
$x=13$ y $y=1$ puede hacer el truco por nosotros minimizando la expresión dada.

Answer 1

Dejemos que $d>0$ sea el máximo común divisor de $a$ y $b$ . Fijar una solución arbitraria $(x_0,y_0)$ de la ecuación $ax+by=N$ . Sea $(x,y)$ sea cualquier solución de esta ecuación. Entonces $a(x-x_0)+b(y-y_0)=0$ Así que $d(x-x_0)|b$ Es decir $x=x_0+kb/d$ para algún número entero $k$ . A la inversa, para cualquier número entero $k$ , $(x_0+kb/d, y_0-ka/d)$ es una solución de la ecuación. Esta solución cuesta $c_1(x_0+ kb/d)+c_2(y_0-ka/d)$ que es $k(c_1b-c_2a)/d$ que el coste de la solución $(x_0,y_0)$ . De ello se deduce que una solución de la ecuación con el mínimo coste es:

• una solución con un mínimo de $x_1$ cuando $c_1b>c_2a$ ,
• una solución con un mínimo de $x_2$ cuando $c_1b<c_2a$ ,
• cualquier solución de la ecuación, cuando $c_1b=c_2a$ .