Реализация грубой силы для рюкзака 0-1

ProgramBox

Реализация грубой силы для рюкзака 0-1

Post author:admin
Запись опубликована:27 августа, 2022
Post category:Вопросы по программированию

#c #algorithm #knapsack-problem

#c #алгоритм #рюкзак -проблема

Вопрос:

Я борюсь с данной задачей почти неделю, но безуспешно нахожу решение, поэтому этот сайт — моя последняя надежда.

У меня проблема с рюкзаком 0-1, в котором 20 предметов с разными значениями и весами, максимальный вес мешка равен 524. Теперь мне нужно реализовать грубую силу, чтобы найти оптимальное подмножество решений из 20 элементов, чтобы общий вес <= 524 и максимальные значения выбранных элементов.

Не могли бы вы указать мне или лучше дать подробную реализацию, чтобы проанализировать, как это работает!! Большое вам спасибо

Ответ №1:

Идея перебора проста:

Создайте все возможные подмножества из ваших 20 предметов, сохраняя только те, которые удовлетворяют вашему ограничению по весу. Если вы хотите проявить фантазию, вы можете даже рассматривать только подмножества, к которым вы не можете добавить что-либо еще, не нарушая ограничения по весу, поскольку только они могут быть правильным ответом. O (2 ^ n)
Найдите подмножество с максимальным весом. линейный по количеству кандидатов, и поскольку у нас есть O (2 ^ n) кандидатов, это O (2 ^ n).

Пожалуйста, прокомментируйте, если вам нужен какой-то псевдокод.

РЕДАКТИРОВАТЬ: Что за черт, вот псевдокод на всякий случай.

   GetCandidateSubsets(items[1..N], buffer, maxw)
  1. addedSomething = false
  2. for i = 1 to N do
  3.    if not buffer.contains(item[i]) and
           weight(buffer)   weight(items[i]) <= maxw then
  4.       add items[i] to buffer
  5.       GetCandidateSubsets(items[1..N], buffer)
  6.       remove items[i] from buffer
  7.       addedSomething = true
  8. if not addedSomething then
  9.    emit amp; store buffer

Обратите внимание, что функция GetCandidateSubsets не очень эффективна даже для реализации методом перебора. Спасибо amit за указание на это. Вы могли бы переработать это, чтобы использовать только комбинации, а не перестановки набора элементов, в качестве оптимизации первого прохода.

   GetMaximalCandidate(candidates[1..M])
  1. if M = 0 then return Null
  2. else then
  3.    maxel = candidates[1]
  4.    for i = 2 to M do
  5.       if weight(candidates[i]) > weight(maxel) then
  6.          maxel = candidates[i]
  7.    return maxel

1. (1) поиск максимального веса O(2^n) также важен, поскольку вам нужно проверить все подмножества. (2) основным преимуществом обратного отслеживания и грубой силы обычно является сложность пространства, сохраняя все возможности, ваша сложность пространства O(2^n) увеличивается, и вы теряете это преимущество. (3) решения в вашем псевдокоде нет O(2^n) , оно есть O(n!) или даже O(n^n)

2. @amit: Правильно, получение максимального элемента будет равно O (2 ^ n), поскольку существует O (2 ^ n) подмножеств для проверки, и код поиска максимального элемента просматривает их все. Вторая критика не так уж важна для меня, поскольку OP на самом деле не указывает, что это вызывает беспокойство. Критика в (3) отмечена; как бы то ни было, я не вложил много работы в этот код.

3. привет, обратите внимание, что если подмножество A имеет 1000 значений и 523 веса, а B имеет 999 значений и 524 веса, то A должно быть оптимальным решением

4. @FinalIllusion: Да, верно. Даже если псевдокод каким-то образом не дает правильного ответа, метод, описанный в пунктах 1 и 2, явно является надежным решением проблемы. Если мой GetCandidateSubsets неэффективен или, как вы, кажется, предполагаете, неверен, выполните поиск в StackOverflow для любой функции для генерации подмножеств из набора элементов. Подойдет любой из них. Удаление подмножеств, которые не являются «полными» в соответствии с ограничением веса, — это просто оптимизация для уменьшения пространства подмножеств-кандидатов.

5. @Patrick87: спасибо за псевдокод! Не могли бы вы, пожалуйста, подробно описать реализацию на c. Я думаю, что я узнаю больше, чем псевдокод

Метки: Реализация грубой силы для рюкзака 0-1