2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 19:47 
Аватара пользователя
Общий знаменатель?

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 21:23 
damir_777 в сообщении #1483320 писал(а):
Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами.

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

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:10 
Аватара пользователя
wrest в сообщении #1483333 писал(а):
Приводим все веса к общему знаменателю
И получаем гигантский рост чисел в задаче.

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:22 
mihaild в сообщении #1483344 писал(а):
И получаем гигантский рост чисел в задаче.

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

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:41 
Аватара пользователя
wrest в сообщении #1483347 писал(а):
Так компьютеру-то всё равно где точка стоит...
Так там не точка двигается, там длина записи числа полиномиально растет. Если у нас были веса вида $\frac{1}{p_i}$ ($p_i$ - $i$-е простое), то после приведения к общему знаменателю веса могут их логарифмических по размеру входа стать полиномиальными. И это убивает все алгоритмы, работающие за полиномиальное от веса время.

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

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение16.09.2020, 23:21 
«!!=ВАЖНО=!! Правила выбора раздела для размещения новой темы» [CS]
maxal в сообщении #93749 писал(а):
Раздел "Программирование" предназначен для обсуждения особенностей программирования и реализаций алгоритмов на языках общего назначения таких как C/C++, Pascal/Delphi, Java, C#, Perl, Python и т.д.
maxal в сообщении #93749 писал(а):
Корневой раздел предназначен для обсуждения алгоритмов (без привязки к языку программирования)

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

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

 
 
 
 Re: Рюкзак с дробным весом предметов
Сообщение17.09.2020, 02:30 
Аватара пользователя
Можно попробовать решить задачу по модулю большого простого числа $p$ не делящего ни один из знаменателей.

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group