Как выбрать взвешенные предметы, чтобы максимизировать прибыль?

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

У меня есть сумка с фиксированной емкостью, скажем С. У нас есть список предметов и их вес. Общий вес всех предметов больше, чем C. Как я могу подобрать максимальное количество предметов в сумке (также пытаясь наилучшим образом заполнить сумку)?

Я подумал о сортировке списка и выбора пунктов, пока мешок не будет полностью заполнен, но в приведенном ниже примере опровергают идею

С = 100 и L = 50, 40, 20, 30.

При Я получаю 20, 30, 40, 50, следовательно, мое распределение будет (20 + 30 + 40) = 90. Но мы можем получить лучшую комбинацию (20 + 30 + 50) = 100.

Проблема может быть решен путем преобразования этой проблемы в рюкзак, придавая весам для каждого элемента, эквивалентного его весу. Есть ли другой алгоритм?

источник

2013-11-23 Neo

Вы хотите увеличить количество предметов, или вы хотите сделать сумку максимально полной? –

@AbhishekBansal: Я хочу сделать сумку максимально полной. – Neo

Существует [метод симплекс] (http://en.wikipedia.org/wiki/Simplex_algorithm). – neeKo

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Это не самое эффективное решение; однако, это a решение.

Я бы -

Сформировать все возможные суммы
Фильтровать суммы от максимальной мощности (bagSize)
Получить максимальную сумму из сгенерированных сумм
Фильтрующих сумм по максимальной сумме
Найти и фильтровать по максимальному количеству товаров, оставшихся

Вот пример любимого языка каждого - Haskell!

import Data.List 

knappsack bagSize items = answers 
    where 
    sums = [(xs, sum xs) | xs <- subsequences items] 
    sumFilter = filter ((<= bagSize) . snd) sums 
    maxSum = foldl max 0 . map (sum . fst) $ sumFilter 
    maxFilter = filter ((== maxSum) . snd) sumFilter 
    maxLen = foldl max 0 . map (length . fst) $ maxFilter 
    lenFilter = filter ((== maxLen) . length . fst) maxFilter 
    answers = lenFilter

источник

2013-11-23 05:30:43 pyrospade

Создание всех возможных сумм - это сложность O (2^n), что делает это решение крайне неэффективным. – neeKo

Поскольку это одно из решений, помимо ранца, я принимаю его, несмотря на его высокую сложность. – Neo

Ничего себе, не видел этого! Обратите внимание, что Haskell выполняет ленивую оценку по умолчанию, поэтому, вероятно, есть хороший способ использовать это для более эффективного алгоритма. К сожалению, мое решение обеспечивает * все * лучшие ответы, поэтому он будет оценивать все. – pyrospade

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

Решите его с использованием технологии динамического программирования, приведенной в Wikipedia.

источник

2013-11-23 05:43:22

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

@Neo Когда вы знаете, что проблема NP трудна, это означает, что нет известного способа решить эту проблему в разумные сроки. Алгоритм динамического программирования является Псевдо-полиномиальным по временной сложности и является наиболее известным алгоритмом для решения таких задач. –

Я не знал, что текущая проблема была NP трудной в начале, я думал, так как я преобразовал проблему в рюкзак, это было NP трудно. Я предполагаю, что bdean20 предоставил ценные комментарии к проблеме и характер требуемого решения. – Neo

Как выбрать взвешенные предметы, чтобы максимизировать прибыль?

ответ

Смежные вопросы