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