Aşağı güc

Siz maşınlar üçün müasir çiplər dizayn edirsiniz. Çiplərin istehsalı asandır, lakin onları enerji ilə təchiz etmək çətindir, çünki mövcud batareyaların çıxış gücləri müxtəlifdir.

Tutaq ki, $n$ maşın var və hər birində iki çip var. Hər çipin işləməsi üçün $k$ batareya lazımdır. Ümumi alınan güc vacib deyil, ancaq maşın yalnız iki çipin çıxış gücü mümkün qədər yaxın olduqda ən yaxşı işləyir. Çipin çıxış gücü onun $k$ batareyasından ən kiçiyidir.

Cəmi $2nk$ batareyanız var; onları çiplərə bölüşdürməlisiniz. Elə ola bilər ki, batareyaları elə bölüşdürmək olmaz ki, hər maşında iki çipin çıxış gücü tam eyni olsun. Amma məqsəd, bütün maşınlar üzrə bu fərqi mümkün qədər azaltmaqdır. Yəni, müştərilərə zəmanət vermək istəyirsiniz ki, hər maşında iki çipin çıxış gücləri arasındakı fərq $d$-dən çox deyil — və $d$ minimalolsun. Bunun üçün optimal bölüşdürməni tapmaq lazımdır.

1-ci nümunəni nəzərdən keçirək. $2$ maşın var, hər biri üçün çip başına $3$ batareya lazımdır, batareyaların çıxış gücləri isə 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12-dir. Məsələn, $1,3,5$ güclü batareyaları bir çipə, $2,4,12$ güclü batareyaları həmin maşının digər çipinə; $6,8,9$ üçüncü çipə, $7,10,11$ isə dördüncü çipə bölmək olar. Çiplərin çıxış gücləri 1, 2, 6, 7 olacaq və hər iki maşında çip fərqi $1$-dir. Bunu başqa üsullarla da əldə etmək olar.