Рюкзак проблема со значениями на предмет и ограниченные предметы

Question

Я пытаюсь решить вариант с рюкзаком, которого раньше не видел.в этом варианте у нас есть вектор v, состоящий из значений на грамм для каждого предмета, и у нас также есть ограниченный вес каждого предмета, и наша цель состоит в том, чтобы найти максимальное значение, которое можно получить, если у нас есть пачка размера M. Я пробовалПодошел жадный, но не нашел решения.я думаю, что самая сложная часть - сделать это в O (n), потому что мы не должны ничего сортировать.У кого-нибудь есть идеи?

Answer 1

Если значение на грамм имеет достаточно узкие границы, вы можете подсчитать-отсортировать или радикально-сортировать, или отсортировать по сегментам по линейному времени по значению на грамм, а затем просто заполнить область в порядке наиболее ценных веществ.Что я имею в виду под разумными пределами?В частности, я имею в виду, что асимптотически меньше значимых «значений на грамм», чем видов веществ.