Matematické Fórum

Pavel Brožek

Mám následující problém:

Je dáno číslo $C=5431698$ a přirozená čísla $a_i,\quad i\in\{1,2,\ldots,23\}$ , přibližně platí $a_{i}\approx350000\cdot(0,965)^{i-1}$ (liší se maximálně o jednotky).

Potřebuji vyřešit rovnici pro $x_i,\quad i\in\{1,2,\ldots,23\}$ :

$C=\sum_{i=1}^{23}a_ix_i$ ,

kde $x_i\in\{0,1,\ldots,10\}$ . Dále vím, že

$\sum_{i=1}^{23}x_i=22$ .

Nejlepší asi bude zjistit řešení zkoušením na počítači , ale nějak mě nenapadá, jak mu to předhodit, aby to nějak efektivně (alespoň v řádu desítek minut) spočítal. Zajímají mě i přibližná řešení, kdy se suma nerovná přímo C, ale liší se třeba o jedna nebo dvě. Pokud bude řešení víc, už by pro mě neměl být problém vybrat ty, která mě zajímají.

Čísla, která uvádím, jsou pouze příklad, můžou se lišit, ale řádově odpovídají hodnotám, pro které to budu počítat. (Pro uvedené hodnoty by to mělo vyjít)

Abych byl konkrétní, uvedu i $a_i$ (od i=1 do i=23):

350000
341250
332719
324401
316291
308384
300674
293157
285828
278682
271715
264923
258299
251842
245546
239407
233422
227587
221897
216350
210941
205667
200526

Předem díky za jakékoliv nápady.

musixx · 19. 01. 2009 15:21

↑ BrozekP: Mozna by se dal pouzit nahodnostni algoritmus. Vezmu pole delky 22 a naplnim jej nahodne cisly z {a_i}. Podivam se, jestli je soucet hodnot v tomto poli roven C. Pokud je soucet vetsi, tak vyberu nejake velke cislo z tohoto pole (treba vetsi nez prumer vsech a-cek) a nahradim ho nejakym mensim (nahodne a pouze z pripustnych a-cek, samozrejme). K tomu se divat, abych nepridal nic po jedenacte (podminka x_i<11). Analogicky pro soucet mensi nez C. Cele se to da vylepsit tim, ze si predpocitam rozdily mezi libovolnymi dvojcemi a-cek a to zahrnu do vyse popsaneho nahodneho vyberu. Ale prvek nahody je nutne zachovat.

Chtel-li bych pak znat i ta x_i, tak staci projit to pole a podivat se, kolikrat tam ktere a-cko je.

Neni to sice deterministricky algoritmus, ale za pokus by to mozna stalo...

Kondr · 19. 01. 2009 15:51

Je to NP-úplné. Pokud je součet dostatečně malý, je efektivní použít algoritmus, který jsem popisovl jinde: http://forum.matweb.cz/viewtopic.php?id=5759 . Při současné úrovni hardware proiterovat 23x pole o velikosti 20MB už nemůže být takový problém (na ty desítky minut byses mohl dostat). Pokud můj i musixxův algoritmus selžou, zkus Googlu vrazit Knapsack Problem a možná něco najdeš.

Matematické Fórum

#1 18. 01. 2009 21:37 — Editoval BrozekP (18. 01. 2009 22:18)

Řešení rovnice v celých číslech

#2 19. 01. 2009 15:21

Re: Řešení rovnice v celých číslech

#3 19. 01. 2009 15:51

Re: Řešení rovnice v celých číslech

Zápatí