Для наборов вида N1 N2 N3 ... 1, из которых можно представить любую сумму, достаточным условием неоптимальности жадного алгоритма будет: Разница номиналов любой пары последующих монет (N1 < N2) меньше чем N2*2 :) В таких случаях нежадный алгоритм может построить сумму N2*2 взяв две монетки N2. А жадный алгоритм всегда будет использовать N1 + a*N3 + b*N4 .... что будет 3 или более монет.
Осталось понять как написать математическое доказательство. Тупею от года в год :(
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Date: 2007-07-08 01:03 am (UTC)Разница номиналов любой пары последующих монет (N1 < N2) меньше чем N2*2 :)
В таких случаях нежадный алгоритм может построить сумму N2*2 взяв две монетки N2. А жадный алгоритм всегда будет использовать N1 + a*N3 + b*N4 .... что будет 3 или более монет.
Осталось понять как написать математическое доказательство. Тупею от года в год :(