Developing.ru

Всем привет!помогите кодом,решить задачу о ранце используя жадный алгоритм

Во-первых, давай полное описание задачи. Во-вторых, выкладывай свои попытки написать код. Помогите подразумевает совет, а не полное написание.

Суть задачи о ранце (о рюкзаке) такова: есть некая ёмкость (назовём её контейнер), которая имеет ограничение по объёму (или по весу) и есть избыточное количество предметов, которыми нужно заполнить этот контейнер. Заполнить его нужно так, чтобы в контейнере не оставалось пустого пространства или объём его был минимальным. При этом каждый предмет имеет свою ценность, поэтому общая стоимость содержимого контейнера должна быть наибольшей.
Здесь можно сразу рассмотреть два частных случая:
1. когда объём каждого предмета одинаков — в этом случае выбираются предметы с наибольшей стоимостью.
2. когда стоимость предметов одинакова — тогда выбираются предметы с наименьшим объёмом.
В остальных случаях нужно вычислять удельную стоимость единицы объёма каждого предмета и выбирать в первую очередь предметы с наибольшим отношением цена/объём, а дальше уже нужно смотреть на заполняемость контейнера. Т.е. подобрать такой набор предметов, чтобы ими максимально заполнить контейнер и добиться максимальной стоимости содержимого.

Так что для начала можно самостоятельно выполнить решение хотя бы для двух частных случаев. Об остальном уже можно будет сообща подумать.

Похоже на упрощёную задачу линейного программирования с целевой функцией Sum (x*C), определяющей максимальную ценность (где С - ценность каждого предмета), одним ограничением на вес Sum (x*M) <= M, и вырожденными ограничениями типа 0 <= x <= A на количество предметов.

Решать можно любым методом линейного программирования. Таковых в интернете масса.