|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.12.2016, 17:15 | #1 |
Новичок
Джуниор
Регистрация: 04.12.2016
Сообщений: 2
|
Свинья-копилка
Помогите пожалуйста.
Известно : в свинью копилку помещается 1000 грамм монет Вводится : достоинство и масса Х(тоже вводится) видов монет Определить : можно ли наполнить копилку монетами указанных типов и если да, определить максимальную сумму. Заранее благодарен
Kami-Sama
|
04.12.2016, 18:19 | #2 | |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
Цитата:
Это одна из NP-трудных задач комбинаторной оптимизации ... не имеющая, в общем случае, приемлемого решения. С чем я вас и поздравляю. В вашем случае задача ослаблена тем, что можно набивать сколько угодно монет одного и того же достоинства. Можете попробовать приближённое решение примерно так: 1. для всех (1,2,3, ...) типов монет вычислить отношение достоинство/вес (Si/Pi)... 2. выбрать монету k с максимальным отношением... 3. набить в копилку N=1000 / Pk таких монет... 4. остаток, если он есть, добивать по тому же принципу монетами с меньшим Si/Pi Последний раз редактировалось olej.tsil; 04.12.2016 в 18:23. |
|
04.12.2016, 18:31 | #3 |
Новичок
Джуниор
Регистрация: 04.12.2016
Сообщений: 2
|
Спасибо большое
Kami-Sama
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сумма и копилка | Окоча Юра | Microsoft Office Excel | 0 | 03.02.2010 10:39 |