задача на упаковку ранца(язык С)

[maxim3535]

Прошу помощи в решении задачи!

Есть ранец, вместимость которого m кг, и есть перечень предметов. У каждого предмета есть два параметра: масса и стоимость. Нужно собрать предметы в рюкзак так, чтобы общая стоимость предметов в рюкзаке была максимальной, но при этом общая масса предметов не превышала вместимость рюкзака.

[BDA]

Самым простым способом является перебор всех вариантов взятия предметов и выбора из них наилучшего. Опять же для упрощения, предположим что предметов не больше 32. Запросим от пользователя вместимость, количество предметов и информацию о них (заведем массив, который хранит массу, стоимость, название для наглядности). Полагаем, что наилучший набор 0, т.е. ни одного предмета, цена 0. Затем в цикле от 1 до 1 << count -1 (счетчик типа unsigned int) считаем массу и стоимость набора (счетчик цикла является битовой маской тех предметов, что в данный момент собираются поместить в рюкзак). Если полученная цена больше предыдущей сохраненной, а масса не превышает вместимости, то набор сохраняется в отдельную переменную. После цикла осталось вывести сохраненный набор на экран.