Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
 Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
Здравствуйте.
Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами. (Вес рюкзака -всегда целое число).
Динамическое программирование здесь не подходит, т.к. работает с целыми числами. Нашел алгоритм с бинарным деревом, но он
оказался для решения 0-1 рюказака. Также в книге Silvano Martino "Knapsack Problem" используется динамическое программирование,
т.к. веса в примерах тоже целые.
Может кто подскажет, или ссылки даст на принцип реализации. В интернете что то по этой теме не то ищется.
15 сен 20, 18:00    [22197691]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
ъъъъъ
Member

Откуда:
Сообщений: 1052
Damir_85,

ты не знаешь, как приводить дроби к общему знаменателю?
15 сен 20, 19:22    [22197739]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
MBo
Member

Откуда:
Сообщений: 75
Damir_85
Что имеется в виду под дробными числами?
Вообще постановку задачи нужно привести.
15 сен 20, 20:08    [22197776]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
MBo
Damir_85
Что имеется в виду под дробными числами?
Вообще постановку задачи нужно привести.

Ну то есть веса предметов могут быть заданы так: 22,5; 30,73; 16,78 и т.д., т.е. в виде десятичных дробей
16 сен 20, 09:46    [22198109]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
постановка задачи, это задача заполнить рюкзак, максимизировав его ценность (для каждого предмета еще задается ценность),
при этом чтобы общий вес предметов не превысил вместимость рюкзака (всегда должна быть целым числом), при этом каждый
предмет может браться в неограниченном количестве.
Почитал про жадный алгоритм, но он дает приближенное решение
16 сен 20, 09:51    [22198114]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
Хотя , если известно, что после запятой количество знаков не будет превышать 3, то нужно умножить все числа на 1000, и вес
рюкзака тоже, потому что он должен пропорционально увеличиться, т.к. увеличиваются веса предметов. Тут уже можно и
динамическим программированием решить, просто не будет ли при этом слишком большая таблица и время вычисления
16 сен 20, 10:03    [22198122]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Гаджимурадов Рустам
Member

Откуда:
Сообщений: 61728
Damir_85> Хотя , если известно, что после запятой количество знаков не будет превышать 3

Это странное допущение...

По сабжу - это какая-то лаба/тестовое задание?
Давно бы уже решили тупым полным перебором.

Posted via ActualForum NNTP Server 1.5

16 сен 20, 16:33    [22198559]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
Гаджимурадов Рустам
Damir_85> Хотя , если известно, что после запятой количество знаков не будет превышать 3

Это странное допущение...

По сабжу - это какая-то лаба/тестовое задание?
Давно бы уже решили тупым полным перебором.

Ничего странного нету. Фактически веса предметов это длины прямоугольных объектов , которые укладываются вдоль заданной
длины рабочего листа, т.е речь идет об укладке предметов в заданный прямоугольник. Графическая программа, в которой можно
задать эти прямоугольники, может показывать длину предметов с точностью до трех знаков после запятой
16 сен 20, 18:35    [22198716]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 51205

Damir_85
речь идет об укладке предметов в заданный прямоугольник.

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

Posted via ActualForum NNTP Server 1.5

16 сен 20, 18:40    [22198720]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
Dimitry Sibiryakov

Damir_85
речь идет об укладке предметов в заданный прямоугольник.

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

ну, к примеру решается симплекс методом с генерацией столбца, когда каждый новый план раскроя получается путем решения подзадачи, что есть задача о рюкзаке. Да это задача раскроя, только я одномерный уже сделал , сейчас делаю двумерный, когда в заданный лист нужно разместить прямоугольники, при этом выполнив требование по спецификации, т.е. по заданному количеству
каждого прямоугольника. Решается аналогичным способом как и одномерный раскрой. Ну вобщем это задача раскроя плитных материалов. Только вот на длинах вот эти числа после запятой и остаются
Реализуется как макрос в среде Corel Draw чтобы вручную не компоновать. Жалко файл не могу прикрепить с реализацией пошаговой в pdf формате. На форуме до 150 Кб можно только, а он весит 413 Кб. Никак ограничения не обходятся по размеру файла?
16 сен 20, 18:48    [22198730]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 51205

Damir_85
Только вот на длинах вот эти числа после запятой и остаются

Опять же уже сказали: умножаем все значения на 1000 и задача внезапно сводится к
целочисленной.

Posted via ActualForum NNTP Server 1.5

16 сен 20, 18:58    [22198733]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 635
Damir_85
Динамическое программирование здесь не подходит, т.к. работает с целыми числами

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

после завершения работы алгоритма делишь все числа назад на 1000. Profit.
16 сен 20, 19:02    [22198736]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1988
asutp2,

а что, так было можно?
16 сен 20, 19:11    [22198740]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Гаджимурадов Рустам
Member

Откуда:
Сообщений: 61728
asutp2> как сказали выше - умножаешь все числа на 1000 и внезапно

Внезапно - он сам же это и сказал.
Хотя для общего случая ограничение
в 3 дробных знака довольно странное.

Posted via ActualForum NNTP Server 1.5

16 сен 20, 19:28    [22198747]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
ъъъъъ
Member

Откуда:
Сообщений: 1052
Гаджимурадов Рустам
Внезапно - он сам же это и сказал.

Вообще-то это я сказал. :)
16 сен 20, 20:26    [22198782]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 635
ъъъъъ
Гаджимурадов Рустам
Внезапно - он сам же это и сказал.

Вообще-то это я сказал. :)
подтверждаю)
16 сен 20, 20:38    [22198787]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Гаджимурадов Рустам
Member

Откуда:
Сообщений: 61728
ъъъъъ> Вообще-то это я сказал. :)

А, про общий знаменатель. :)
Виноват, не обратил внимание.

Posted via ActualForum NNTP Server 1.5

16 сен 20, 20:58    [22198796]     Ответить | Цитировать Сообщить модератору
 Re: Рюкзак с дробным весом предметов  [new]
Damir_85
Member

Откуда:
Сообщений: 242
ok,спасибо. Попробую этот вариант
вчера, 09:48    [22198933]     Ответить | Цитировать Сообщить модератору
Все форумы / Delphi Ответить