LINUX.ORG.RU

Перебор 2^1000 комбинаций

 ,


0

1

Всем привет! Столкнулся с задачей из раздела оптимизации и комбинаторики, а именно- задача рюкзака. Суть в следующем - имеется набор предметов, ограничение по весу, вес и ценность каждого предмета. Но в отличие от классической задачи рюкзака, у каждого предмета есть два варианта цены и веса.

Т.е. например рюкзак может взять 20кг У нас есть Картошка 10кг стоимостью 100р Картошка 20кг стоимость 300р Бутылка пива 1кг стоимость 500р Бутылка пива 1кг стоимостью 100р и т.д. Т.е. для каждого предмета два варианта

Собственно как сейчас решаю задачу - из двух массивов входных данных получаю уникальные комбинации предметов (2^n комбинаций), загоняю каждую комбинацию в алгоритм рюкзака (использую “жадный алгоритм”), получаю массив выходных данных, беру решение с наибольшой “ценностью” - это и есть оптимальный вариант. Все работает нормально, если у нас не больше 10-15 предметов. Но если предметов становится 20,50,100,1000 - это 2^1000 комбинаций, и всё уходит в глубокую кому. Не получается даже завершить генерацию уникальных комбинаций.

Подскажите пожалуйста, как решиь данную проблему? Возможно, у вас есть какое-то другое видение на решение данной задачи?

Уникальные комбинации генерирую так:

E=[]
off = [1 2 3 4 5]
on = [a b c d e]
for choices in itertools.product([0, 1], repeat=len(off)):
 E.append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])

Но в отличие от классической задачи рюкзака, у каждого предмета есть два варианта цены и веса.

Если у задачи есть отличие от всем известной формулировки, может стоило бы ее все-таки подробно сформулировать? Что найти надо, какие ограничения на веса, стоимости, сколько предметов?

И да, как начинающий телепат предположу, что ты хочешь научиться решать обычную задачу о рюкзаке динамическим программированием, а потом чуть-чуть поменять алгоритм.

metar ★★★ ()
Ответ на: комментарий от metar

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

cdshines ★★★★★ ()

Возможно, у вас есть какое-то другое видение на решение данной задачи?

Загруби параметры (например, поделить на число и взять целое) и динамическое программирование.

использую ”жадный алгоритм”

Там же один проход и даже перебирать ничего не надо, разве нет?

i-rinat ★★★★★ ()

Суть задачи

Подробно про саму задачу: Есть рюкзак с определенной вместимостью, есть предметы, который надо уложить в рюкзак, у каждого предмета есть две пары «вес-ценность», и взять можно только ОДНУ вариацию одного предмета. Поэтому и стоит задача загнать в алгоритм расчета рюкзака все возможные комбинации. Т.е. например сначала загоняем все предметы с 1-ым вариантом «вес-ценность», потом у первого предмета меняем атрибуты «вес-ценность» на второй, а у остальных оставляем тоже самое, и т.д. Отсюда и получается 2^n

ad_pro ()
Ответ на: Суть задачи от ad_pro

Т.е. например сначала загоняем все предметы с 1-ым вариантом «вес-ценность», потом у первого предмета меняем атрибуты «вес-ценность» на второй, а у остальных оставляем тоже самое, и т.д. Отсюда и получается 2^n

ну бред же. как только положили в рюкзак одну вариацию предмета - убираем из множества доступных остальные (просто выкидываем, ставим запредельный вес, ...). И не надо перебирать 2^n раз всю задачу.

arkhnchul ★★ ()
Ответ на: Суть задачи от ad_pro

стоит задача загнать в алгоритм расчета рюкзака все возможные комбинации

«все возможные комбинации» просчитать нельзя — никаких мощей не хватит. Это np-hard задача. А на питоне тебе лучше не список делать, а сделать генератор. Это сэкономит память.

true_admin ★★★★★ ()
Ответ на: Суть задачи от ad_pro

На всякий случай повторюсь. Тебе действительно нужно понять, как работает вот это решение обычной задачи о рюкзаке. После этого ты просто будешь считать не функцию от количества предметов N и вместимости W, а еще и от флажка 0/1. Решение будет иметь ту же самую асимптотику, что и обычная задача о рюкзаке.

metar ★★★ ()
Последнее исправление: metar (всего исправлений: 1)
Ответ на: комментарий от true_admin

Да, собственно, странная постановка: тс должен знать, что np-полная (во многих описаниях задачи указано). А, значит, искать уже не _точное_, а _приближенное_ решение.

anonymous ()
Ответ на: комментарий от metar

Сделай diff с тем, что было по ссылке:

// Input:
// Values (stored in array v)  -- PAIRS OF THEM
// Weights (stored in array w) -- PAIRS OF THEM
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w, 0] := 0
  m[0, w, 1] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    for x from 0 to 1 do
      for y from 0 to 1 do
        if j >= w[i, x] then
          m[i, j, x] := max(m[i-1, j, y], m[i-1, j-w[i], y] + v[i, x])
        else
          m[i, j, x] := m[i-1, j, y]
        end if
      end for
    end for
  end for
end for

metar ★★★ ()
Ответ на: комментарий от anonymous

Да, собственно, странная постановка: тс должен знать, что np-полная (во многих описаниях задачи указано). А, значит, искать уже не _точное_, а _приближенное_ решение.

Каким образом существование точного решения зависит от класса сложности задачи?

metar ★★★ ()
Ответ на: комментарий от metar

Откуда такой вывод именно про «существование»?

Давай спорь с: s//адекватность желания найти/.

anonymous ()
Ответ на: комментарий от metar

я правильно понял, что в

Values (stored in array v)
и в
Weights (stored in array w)
мы записываем ВСЕ пары значений для всех предметов, т.е. в нашем случае (когда у каждого предмета существует две пары «вес-ценность») длина массива будет 2*кол-во предметов? А в
Number of distinct items (n)
мы указываем сколько у нас УНИКАЛЬНЫХ предметов?

ad_pro ()
Ответ на: комментарий от anonymous

Как-то не очень понятно, почему NP-полнота заставляет тебя думать о приближенных вычислениях, а не (оставшиеся неизвестными) ограничения на входные данные, вот и все.

metar ★★★ ()
Ответ на: комментарий от metar

о приближенных вычислениях

Подразумевалось, что это - способ устранения «странная постановка:»

а не (оставшиеся неизвестными)

Действительно, почему нужно искать решение адекватное условию, а не уточнять условия.. Хотя зачем уточнять условия, если можно уточнить нужно ли вообще решать задачу).

anonymous ()

knapsack, лолка. Не knackpack.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.