Рюкзак с дробным весом предметов

[damir_777]

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

[StaticZero]

Общий знаменатель?

[wrest]

damir_777 в сообщении #1483320 писал(а):

Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами.

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

[mihaild]

wrest в сообщении #1483333 писал(а):

Приводим все веса к общему знаменателю

И получаем гигантский рост чисел в задаче.

[wrest]

mihaild в сообщении #1483344 писал(а):

И получаем гигантский рост чисел в задаче.

Так компьютеру-то всё равно где точка стоит... Что 100 грамм предмет и 100 килограмм рюкзак, что килограмм предмет и тонна рюкзак.

[mihaild]

wrest в сообщении #1483347 писал(а):

Так компьютеру-то всё равно где точка стоит...

Так там не точка двигается, там длина записи числа полиномиально растет. Если у нас были веса вида $\frac{1}{p_i}$ ($p_i$ - $i$-е простое), то после приведения к общему знаменателю веса могут их логарифмических по размеру входа стать полиномиальными. И это убивает все алгоритмы, работающие за полиномиальное от веса время.

[damir_777]

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

[GAA]

«!!=ВАЖНО=!! Правила выбора раздела для размещения новой темы» [CS]

maxal в сообщении #93749 писал(а):

Раздел "Программирование" предназначен для обсуждения особенностей программирования и реализаций алгоритмов на языках общего назначения таких как C/C++, Pascal/Delphi, Java, C#, Perl, Python и т.д.

maxal в сообщении #93749 писал(а):

Корневой раздел предназначен для обсуждения алгоритмов (без привязки к языку программирования)

Из описания раздела «Олимпиадные задачи (CS)»: «… Обсуждение нетривиальных и нестандартных учебных задач».

Тема перенесена из раздела «Программирование» в «Олимпиадные задачи (CS)». В разделе «Программирование» создавайте, пожалуйста, темы, посвящённые языкам программирования высокого уровня (ЯВУ) общего назначения. Темы, посвящённые алгоритмам [без привязки к языку программирования], создавайте, пожалуйста, в корне или в разделе «Олимпиадные задачи (CS)» (если тема посвящена конкретной нестандартной/нетривиальной задаче).

[maxal]

Можно попробовать решить задачу по модулю большого простого числа $p$ не делящего ни один из знаменателей.

[_Swetlana]

Как раз такую задачу смотрю.
Если стоимости были целые, то нужно было воспользоваться следующим приёмом: считать минимальный вес при данной набранной стоимости.