Równanie diofantyczne - 3 zmienne

[dvrx47]

Czy jest jakiś normalny sposób na rozwiązanie zadania: dla danych \(\displaystyle{ a,b, n}\) (dodatkowo można założyć, że \(\displaystyle{ a < b}\) ) (wszystkie liczby nieujemne, całkowite) znaleźć takie nieujemne, całkowite \(\displaystyle{ k_0, k_1, k_2}\), spełniające równanie \(\displaystyle{ k_0 + a \cdot k_1 + b \cdot k_2 = n}\),
i, że suma \(\displaystyle{ k_0 + k_1 + k_2}\) jest najmniejsza z możliwych.

wystarczy znaleźć najmniejszą sumę.

[a4karo]

Fajne zadanko.

Wyobraź sobie, że masz z dużego pojemnika przelać do swojego wiaderka \(\displaystyle{ n}\) litrów mleka. Masz do dyspozycji miarki \(\displaystyle{ 1,a,b}\)litrów .(powiedzmy ,że \(\displaystyle{ a<b}\).

Jak będziesz przelewal,żeby się najmniej narobić ?

[dvrx47]

intuicja podpowiada, że maksymalną możliwą ilość zapełniam największą miarką, później z tego co zostanie do zapełnienia największyą z pozostałych itd. ale to nie koniecznie będzie prawda, bo jeśli będę miał miarki \(\displaystyle{ {1, 3, 4}}\) i n będzie równe 6 to jak zrobię to zachłannie (4,1,1) to wyjdzie mi suma 3, a jak wezmę dwa razy średnie wiadro to suma będzie równa 2 - dlatego nie wiem jak się za to zabrać

[a4karo]

Fakt. Trzeba się chyba pobawić resztami z dzielenia \(\displaystyle{ n}\) przez \(\displaystyle{ a}\) i \(\displaystyle{ b}\)