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

Question

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

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

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

Answer 1

Идея грубой силы проста:

1. Создайте все возможные подмножества из ваших 20 предметов, сохранив только те, которые удовлетворяют вашему ограничению веса.Если вы хотите проявить фантазию, вы можете даже рассмотреть только те подмножества, к которым вы не можете добавить ничего, не нарушая ограничения по весу, поскольку только они могут быть правильным ответом.O (2 ^ n)
2. Найти подмножество с максимальным весом.линейный с точки зрения количества кандидатов, и, поскольку у нас есть 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 & store buffer

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

  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