Здравствуйте.
Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами. (Вес рюкзака -всегда целое число).
Динамическое программирование здесь не подходит, т.к. работает с целыми числами. Нашел алгоритм с бинарным деревом, но он
оказался для решения 0-1 рюказака. Также в книге Silvano Martino "Knapsack Problem" используется динамическое программирование,
т.к. веса в примерах тоже целые.
Может кто подскажет, или ссылки даст на принцип реализации. В интернете что то по этой теме не то ищется.

Ну то есть веса предметов могут быть заданы так: 22,5; 30,73; 16,78 и т.д., т.е. в виде десятичных дробей

постановка задачи, это задача заполнить рюкзак, максимизировав его ценность (для каждого предмета еще задается ценность),
при этом чтобы общий вес предметов не превысил вместимость рюкзака (всегда должна быть целым числом), при этом каждый
предмет может браться в неограниченном количестве.
Почитал про жадный алгоритм, но он дает приближенное решение

Хотя , если известно, что после запятой количество знаков не будет превышать 3, то нужно умножить все числа на 1000, и вес
рюкзака тоже, потому что он должен пропорционально увеличиться, т.к. увеличиваются веса предметов. Тут уже можно и
динамическим программированием решить, просто не будет ли при этом слишком большая таблица и время вычисления

Ничего странного нету. Фактически веса предметов это длины прямоугольных объектов , которые укладываются вдоль заданной
длины рабочего листа, т.е речь идет об укладке предметов в заданный прямоугольник. Графическая программа, в которой можно
задать эти прямоугольники, может показывать длину предметов с точностью до трех знаков после запятой

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

ну, к примеру решается симплекс методом с генерацией столбца, когда каждый новый план раскроя получается путем решения подзадачи, что есть задача о рюкзаке. Да это задача раскроя, только я одномерный уже сделал , сейчас делаю двумерный, когда в заданный лист нужно разместить прямоугольники, при этом выполнив требование по спецификации, т.е. по заданному количеству
каждого прямоугольника. Решается аналогичным способом как и одномерный раскрой. Ну вобщем это задача раскроя плитных материалов. Только вот на длинах вот эти числа после запятой и остаются
Реализуется как макрос в среде Corel Draw чтобы вручную не компоновать. Жалко файл не могу прикрепить с реализацией пошаговой в pdf формате. На форуме до 150 Кб можно только, а он весит 413 Кб. Никак ограничения не обходятся по размеру файла?

ok,спасибо. Попробую этот вариант