Существует вариация задачи о ранце, когда все прибыли равны 1. Кажется, что ее можно решить гораздо быстрее, чем классическая дискретная (0-1) задача о ранце, но как?Будет ли работать только жадный алгоритм (на каждую итерацию кладите объект с минимальным весом в рюкзак)?
Мне следовало бы так думать.
Интуитивно, учитывая, что все прибыли равны единице, со стороны прибыли вам безразлично, какие товары вы выбираете, вы просто хотите столько, сколько сможете.Жадный алгоритм даст вам именно это.