Как реализовать применимый алгоритм встречи в среднем для 0-1 рюкзак?

Question

Я сейчас изучающую проблему рюкзак (кП) и найти алгоритм встречи в среднем, описанный в Wikipedia немного непонятно, как реализовать его в теоретической сложности времени $ ^ * 2}) $ ? Я могу понять алгоритм для проблемы сопутствующих сумм (SSP), которая является определенным примером 0-1 кП, но для обобщенной проблемы может быть что-то не так с шагом:

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

.

Как я понимаю, это для поиска (например, делать бинарный поиск) на комбинированные веса всех подмножеств B, который принимает в систему для каждого поиска. Но после того, как знание, какие подмножества имеют комбинированный вес меньше, чем W, как найти одно из величайших ценностей? Если поиск по значению подмножеств с весом $ O ^ * (2 ^ {n / 2}) $ , но что-то вроде $ o ^ * (2 ^ n) $ .

Даже если он начинает показывать подмножество наибольшего значения (легко для таблицы), сначала без сужения при комбинированном весе, после этого проверка веса, вероятно, повернет ложь и, следовательно, для других подмножеств Номер, кажется, связан с размером таблицы линейно.

Теперь я могу предположить, что общая стоимость, и комбинированная веса сильно положительна коррелирована, так что после нахождения подмножества с максимально допустимым весом требуется только постоянное время для поиска вокруг этого подмножества для точного одно из наибольшего значения. Но я не удовлетворен этим объяснением. Так что у кого есть лучшие идеи по этому вопросу?

PS: Я прочитал оригинальную газету Horowitz, Ellis и Sahni, Sartaj, но я обнаружил, что проблема определена, есть решение, а не распространенную задачу оптимизации. Может быть, кто-то может предоставить идеи в этом направлении.

Answer 1

Во-первых, предварительно предлогайте веса каждого подмножества $ B $ .

Сортируйте их по весу и поместите вес и подмножество параллельных массивов, чтобы $ w [i]= вес $ и $ S [i]= подмножество $ .

Затем сделайте другой параллельный массив, чтобы $ Best [i] $ - это индекс $ j $ Из набора наибольшего значения такого, что $ J <= I $ .Вы можете сделать это одним сканированием от $ i= 0 $ вверх, запоминая наибольшее значение, которое видно на каждом шаге.

Теперь для поиска $ B $ , вы делаете двоичный поиск в $ W $ , чтобы найтиМаксимально допустимый вес и получите лучший набор из того же индекса в $ Best $