Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Есть рюкзак некоторой вместимости и множество предметов заданного веса. У каждого предмета своя награда. Нужно собрать рюкзак таким образом, чтобы суммарная награда была максимальной. Однако есть проблема - награда предмета не детерминирована и есть функция от имеющегося содержимого рюкзака и очереди помещения в рюкзак. Хочется построить алгоритм способный находить решение хотя-бы для множества из 20 предметов за несколько секунд.
Если на уровне метафоры - то пусть будет алгоритм обжоры. Есть праздничный стол и человек. Награда - "вкусность" блюда. Нужно оптимально придумать чтоб такое съесть, чтобы получить максимальное удовольствие пока не насытился. Ну и предполагаем что съесть торт, если уже наелся пирожных менее вкусно, чем съесть торт, если до этого пил воду.
Что-то я пока что думал-думал, но ничего кроме полного перебора не придумал. Буду благодарен за помощь.
ИСН
Re: Задача о рюкзаке с функциональной наградой
25.11.2016, 18:24
Задача о рюкзаке даже без Вашего усложнения является NP-полной, а с ним - ну уж всяко не проще.
Mihaylo
Re: Задача о рюкзаке с функциональной наградой
26.11.2016, 06:20
Последний раз редактировалось Mihaylo 26.11.2016, 06:21, всего редактировалось 2 раз(а).
Задача о рюкзаке даже без Вашего усложнения является NP-полной, а с ним - ну уж всяко не проще.
Далеко не факт. Нужно вычислить отношение "награда/вес" для каждого предмета и выбрать лучшие предметы по этому показателю. Их и надо запихивать в рюкзак.
Sphinx Pinastri
Re: Задача о рюкзаке с функциональной наградой
26.11.2016, 08:32
Так ведь — это мелочь, и задача такого размера вполне решается полным перебором.
atlakatl
Re: Задача о рюкзаке с функциональной наградой
26.11.2016, 08:52
Sphinx Pinastri
Sphinx Pinastri
Re: Задача о рюкзаке с функциональной наградой
26.11.2016, 09:09
Предмет либо кладут, либо не кладут. И порядок укладки на результат не влияет. Обозначим наличие каждого предмета двоичным разрядом. Получается укладок.