Всем доброго дня!
Необходимо решить классическую задачу о рюкзаке(из множества предметов, каждый из которых имеет свою стоимость и ценность, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную ценность при одновременном соблюдении ограничения на суммарную стоимость):
(∑pjxj) –> max,
∑wjxj ≤ c,
xj = {0;1}, j = 1..n, где pj - ценность вещи j, wj - стоимость вещи j.
Мне известны 4 метода решения:
1. Динамическое программирование. 2. Жадный алгоритм. 3. Метод ветвей и границ. 4. Генетический алгоритм.
Во всех источниках вводится ограничение на целочисленность данных pj, wj, с; в моей задаче: wj и с имеют денежный эквивалент. Хотя от этого еще можно избавится, домножив на 100, то что делать с размерами данных (10000, 20000, 100000), я не знаю, во всех примерах описаны данные до 100.
Трудоемкость динамического программирования O(n*c), и если с порядка сотен тысяч при n до 20,то получается многовато памяти, жадный алгоритм не дает оптимального решения в дискретном случае.
Подскажите, пожалуйста, какой алгоритм применим в этом случае(при таких огромных wj и с), с возможностью запрограммировать его на Delphi или C?

Заранее благодарен!

C#C++По моему, условие как раз для Симплекс-метода, а может, для Метода потенциалов (транспортная задача)...
Точно не помню

Нигде в источниках по knapsack problem 0-1 симплекс-метод для этой задачи не описан, к тому же, по-моему, он тоже труден для программирования!

White Owl Nicky_NВо всех источниках вводится ограничение на целочисленность данных pj, wj, с; в моей задаче: wj и с имеют денежный эквивалент. Хотя от этого еще можно избавится, домножив на 100, то что делать с размерами данных (10000, 20000, 100000), я не знаю, во всех примерах описаны данные до 100.И что тебя в этом всем смущает?
Во первых, никакого ограничения на целочисленность данных на самом деле нет, возможно ее ввели в твоем учебнике чтобы было проще объяснить алгоритм, но на самом деле целая у тебя буханка хлеба кладется в рюкзак или половинка - разницы для алгоритма укладки нету никакой.
Во вторых, примеры это примеры, на них надо смотреть, но они не руководство к действию и уж тем более не ограничитель чего-либо.
Я просмотрел не один учебник, форум и сайт (в т. ч. даже иностранные источники) и везде(!), везде принимают ограничение на целочисленность параметров(проверить легко: наберите в гугле "задача о рюкзаке", откройте любые ссылки и Вы убедитесь в этом сами). Меня смущает то, что многие алгоритмы(динамич. прогр., жадный алгоритм) дают квазиоптимальное решение(т.е. почти оптимальное, но не на 100%). Трудность других же зависит от параметров (от n и c) и чем больше эти параметры, тем возрастает сложность алгоритма, а у меня они большие.
Я и хочу узнать, если какой-нибудь алгоритм, дающий оптимальные решения, сложность которого меньше, чем О(n*c).

Извините, я оговорился: динамическое программирование дает как раз оптимальное решение, но со сложностью О(n*c), т.е. в моем случае - при n = 15 и c = 100000 сложность О(1500000).

White Owl Nicky_NЯ просмотрел не один учебник, форум и сайт (в т. ч. даже иностранные источники) и везде(!), везде принимают ограничение на целочисленность параметровА что такое параметр? Веса предметов и их стоимости это не параметры, а данные. На целочисленность данных там ограничений нигде не ставят? Нет?
Да, Вы правы это данные, как раз на их целочисленность и ставят ограничения!

Ilya Anfimov
On Wed, Mar 12, 2008 at 05:47:07PM +0000, Nicky_N wrote:
>
> Автор: [1]Nicky_N
> Извините, я оговорился: динамическое программирование дает как раз
> оптимальное решение, но со сложностью О(n*c), т.е. в моем случае - при
> n = 15 и c = 100000 сложность О(1500000).

И что, полтора миллиона -- это много что-ли?

Posted via ActualForum NNTP Server 1.4

Ну вообще-то, да!
Уважаемые, Вы с этими алгоритмами сталкивались когда-нибудь?

White Owl Nicky_N White Owl Nicky_NЯ просмотрел не один учебник, форум и сайт (в т. ч. даже иностранные источники) и везде(!), везде принимают ограничение на целочисленность параметровА что такое параметр? Веса предметов и их стоимости это не параметры, а данные. На целочисленность данных там ограничений нигде не ставят? Нет?
Да, Вы правы это данные, как раз на их целочисленность и ставят ограничения!дааа..... теоретик...

Ну давай по рабоче-крестьянски посмотрим на твою задачу. Давай попробуем ее решить а не рассуждать о ней. Вот на чем ты ее хочешь решать? Дельфи-Си? Выбирай любой и задай для начала массивы для своих p (ценности вещей) и w (стоимости вещей) и ограничивающую константу c - максимальную стоимость. Массивы с данными у тебя будут размером 15 элементов, а какой тип данных ты выберешь для этих массивов и для константы?

int64 или double

White Owl Nicky_N White OwlМассивы с данными у тебя будут размером 15 элементов, а какой тип данных ты выберешь для этих массивов и для константы?
int64 или doubleНо все таки, int64 или double?
double
Извините, я не могу понять, при чем здесь это? проблема не в кодировании, а в алгоритме!

авторТо мы сможем отдать этот массив в функцию которая запустит алгоритм укладки рюкзака методом динамического программирования? Этот алгоритм будет работать или нет?
Да.

White Owl Nicky_N авторТо мы сможем отдать этот массив в функцию которая запустит алгоритм укладки рюкзака методом динамического программирования? Этот алгоритм будет работать или нет?
Да.Но ведь double это не целочисленный тип данных. Как же алгоритм будет работать если в нем есть ограничение на целочисленность?
возьмите int64.

Frenzy Nicky_NВсем доброго дня!
Необходимо решить классическую задачу о рюкзаке(из множества предметов, каждый из которых имеет свою стоимость и ценность, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную ценность при одновременном соблюдении ограничения на суммарную стоимость):
(∑pjxj) –> max,
∑wjxj ≤ c,
xj = {0;1}, j = 1..n, где pj - ценность вещи j, wj - стоимость вещи j.

примеры с недискретным х нигде не приводятся, потому что в этом случае задача становится намного более тривиальной, если х неограничены, то выбираем х с наибольшим соотношением pj/wj - и набираем полный рюкзак самых выгодных иксов (т.е. максимум сколько влезает в с). если х ограничены (как у вас единицей в вашем условии), то сортируем иксы по убыванию выгодности (выгодность pj/wj), и берем максимум самых выгодных иксов, затем максимум вторых по выгодности и так далее пока не заполним рюкзак (т.е. пока не получим общую цену иксов с).

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

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

White Owlгы.... Я понял откуда у нашего студента такие странные идеи:
456-ая страница того самого учебника который читает Nicky_NДискретная задача о рюкзаке (0-1 knapsack problem) формулируется сле-
дующим образом. Вор во время ограбления магазина обнаружил n предметов.
Предмет под номером i имеет стоимость vi грн. и вес wi кг, где и vi, и wi — целые
числа. Нужно унести вещи, суммарная стоимость которых была бы как можно
большей, однако грузоподъемность рюкзака ограничивается W килограммами,
где W — целая величина. Какие предметы следует взять с собой?Я хочу посмотреть на тот ювелирный магазин в котором каждое колечко, брошка или кулончик весят один килограмм.

Nicky_N, ты слишком много читаешь учебников. Вот есть люди которые читают слишком мало, а ты их читаешь слишком много.
Уважаемый White Owl, давайте я сам разберусь сколько и какие книги мне читать, если у Вас есть дельные советы,выскажите их, а свои язвительные замечания прошу оставить при себе.

Frenzy Nicky_Nвы говорите о классическом жадном алгоритме, для дискретной задачи он не дает оптимального решения(контрпримеры - стр 456-457 и тут).

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