| Автор | Задача по информатике |
|---|
помогите решить задачу
Для подготовки заключительного этапа Russian Code Cup организаторам потребовалось отправить на место проведения n предметов. Для каждого предмета известна его масса в граммах mi.
Для отправки решено было воспользоваться почтовой службой «Суперэкспресс». Служба принимает к пересылке бандероли, в каждой из которых может пересылаться один или несколько предметов. При этом масса бандероли равна сумме масс пересылаемых в ней предметов.
Пересылка бандероли стоит 1 рубль за грамм, за исключением бандеролей, которые попадают под действие специального предложения. А именно, если бандероль весит ровно один килограмм, то стоимость ее пересылки составляет P рублей.
Организаторы Russian Code Cup хотят переслать все предметы, затратив минимальную возможную сумму денег. Помогите им распределить предметы по бандеролям, чтобы добиться этого.
Формат входных данных
Первая строка содержит два целых числа: n и P (1 ≤ n ≤ 14; 1 ≤ P ≤ 1000) — количество предметов и стоимость пересылки бандероли в рамках специального предложения. Вторая строка содержит n целых чисел: m1, m2, ..., mn (1 ≤ mi ≤ 1000 для всех i от 1 до n).
Формат выходных данных
Выведите одно число — минимальную суммарную стоимость пересылки всех предметов в рублях.
Желательно код на С++ кто может. |
| [Сообщение удалено смотрителем Marevick // Оффтоп] |
| чем то задачу о рюкзаке напоминает, аналогичная задача на зачет по проге и у меня) увы, решения не знаю, но темку апну и возьму на заметку) |
| такого в школе не учат) |
для letalis:
ну так в школе и нет зачетов) школа-лафа) |
| это с олимпы от мэйл ру.Кто поможет. Я написал решение но оно некатит по времени.Слишком много. Но суть такая что мы перебираем все суммы и ищем есть ли равная 1кг если да то выпиливаем используемые элементы и идём дальше. |
| кто нить помогите решить задачу |
Нужно анализировать пример, понять, как это получилось...
Без примера входных и выходных прогресса не будет!
_______________
Великая Чумка такого в школе не учила, только в паскале писать умеет... |
| сечас кину пример |
5 800
100 200 300 400 500 1300
5 800
400 400 400 400 400 2000 |
| что неужели никто не поможет? |
| ну апну мб кто поможет |
такого в школе не учат)
у нас в 8 классе курсовая сложнее была... |
| ну давай тогда скажи как решать эту задачу? |
| Все комбинаторные задачи решаются методом простого перебора. Если достаточно приближенного решения то возможно использование различными алгоритмами. Я подобную задачу когда-то решал генетическим алгоритмом. Где-то исходник даже валяется, если очень надо,я могу поискать, но алгоритм отнюдь не тривиальный. |
| тема закрыта by Гроза_всех (2011-05-20 17:11:58) |
|---|
