Свинья-копилка

[VovaMuk]

Помогите пожалуйста.
Известно : в свинью копилку помещается 1000 грамм монет
Вводится : достоинство и масса Х(тоже вводится) видов монет
Определить : можно ли наполнить копилку монетами указанных типов и если да, определить максимальную сумму.

Заранее благодарен

[olej.tsil]

Сообщение от VovaMuk

Помогите пожалуйста.
Известно : в свинью копилку помещается 1000 грамм монет
Вводится : достоинство и масса Х(тоже вводится) видов монет
Определить : можно ли наполнить копилку монетами указанных типов и если да, определить максимальную сумму.

В общем виде ваша задача - это хорошо известная задача о ранце (ещё называемая: задача о рюкзаке) ... почитайте по ссылке.
Это одна из NP-трудных задач комбинаторной оптимизации ... не имеющая, в общем случае, приемлемого решения.
С чем я вас и поздравляю.

В вашем случае задача ослаблена тем, что можно набивать сколько угодно монет одного и того же достоинства.
Можете попробовать приближённое решение примерно так:
1. для всех (1,2,3, ...) типов монет вычислить отношение достоинство/вес (Si/Pi)...
2. выбрать монету k с максимальным отношением...
3. набить в копилку N=1000 / Pk таких монет...
4. остаток, если он есть, добивать по тому же принципу монетами с меньшим Si/Pi

[VovaMuk]

Спасибо большое