Задача о рюкзаке с функциональной наградой

[Phoen1x]

Есть рюкзак некоторой вместимости и множество предметов заданного веса. У каждого предмета своя награда. Нужно собрать рюкзак таким образом, чтобы суммарная награда была максимальной. Однако есть проблема - награда предмета не детерминирована и есть функция от имеющегося содержимого рюкзака и очереди помещения в рюкзак. Хочется построить алгоритм способный находить решение хотя-бы для множества из 20 предметов за несколько секунд.

Если на уровне метафоры - то пусть будет алгоритм обжоры. Есть праздничный стол и человек. Награда - "вкусность" блюда. Нужно оптимально придумать чтоб такое съесть, чтобы получить максимальное удовольствие пока не насытился. Ну и предполагаем что съесть торт, если уже наелся пирожных менее вкусно, чем съесть торт, если до этого пил воду.

Что-то я пока что думал-думал, но ничего кроме полного перебора не придумал. Буду благодарен за помощь.

[ИСН]

Задача о рюкзаке даже без Вашего усложнения является NP-полной, а с ним - ну уж всяко не проще.

[Mihaylo]

ИСН в сообщении #1171652 писал(а):

Задача о рюкзаке даже без Вашего усложнения является NP-полной, а с ним - ну уж всяко не проще.

Далеко не факт. Нужно вычислить отношение "награда/вес" для каждого предмета и выбрать лучшие предметы по этому показателю. Их и надо запихивать в рюкзак.

[Sphinx Pinastri]

Так ведь $2^{20}$ — это мелочь, и задача такого размера вполне решается полным перебором.

[atlakatl]

Sphinx Pinastri
$20!$

[Sphinx Pinastri]

Предмет либо кладут, либо не кладут. И порядок укладки на результат не влияет. Обозначим наличие каждого предмета двоичным разрядом. Получается $2^n$ укладок.

[Brukvalub]

Sphinx Pinastri в сообщении #1171754 писал(а):

порядок укладки на результат не влияет.

Как "не влияет"?

Phoen1x в сообщении #1171651 писал(а):

награда предмета не детерминирована и есть функция от имеющегося содержимого рюкзака и очереди помещения в рюкзак.

[grizzly]

atlakatl в сообщении #1171751 писал(а):

Sphinx Pinastri
$20!$

Кто больше?
Всех вариантов в несколько раз больше, хотя, в общем, порядок примерно такой.