ecuatii diofantice

[•ucc_5]

Am intalnit o problema care cere rezolvarea ecuatiei a1*x1+a2*x2+a3*x3+...+an*xn=c; x,a,c apartin lui N (in cazul acesta);
Dupa ceva cercetarii am aflat ca aceasta se numeste ecuatie diofantica . Din pacate am gasit ceva despre modul in care se rezolva dar nu inteleg mare lucru si mai ales nu inteleg cum as putea implementa rezolvarea intr-un algoritm.
Ma poate ajuta cineva ? nu vreau algoritmul, vreau doar niste explicatii in legatura cu modul de rezolvare si niste sugestii pentru a transpune in program.

[•Cosmin]

Asta e o varinata de "integer linear programming" si e NP, deci probabil nu o sa gasesti prea repede algoritmi polinomiali pentru a o rezolva.

Poate problema ta are ceva restrictii in plus si se poate rezolva mai usor. Scrie problema initiala si vedem daca sunt solutii mai bune.

[•ucc_5]

Singurele restrictii sunt ca numarul de "X"-uri e maxim 18 si am mai observat un lucru si anume.
Eu am incercat sa fac cu backtracking dar iese din timp.