2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Рюкзак с дробным весом предметов
Сообщение15.09.2020, 19:00 


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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 19:47 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Общий знаменатель?

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 21:23 


05/09/16
12264
damir_777 в сообщении #1483320 писал(а):
Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами.

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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:10 
Заслуженный участник
Аватара пользователя


16/07/14
9401
Цюрих
wrest в сообщении #1483333 писал(а):
Приводим все веса к общему знаменателю
И получаем гигантский рост чисел в задаче.

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:22 


05/09/16
12264
mihaild в сообщении #1483344 писал(а):
И получаем гигантский рост чисел в задаче.

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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение15.09.2020, 23:41 
Заслуженный участник
Аватара пользователя


16/07/14
9401
Цюрих
wrest в сообщении #1483347 писал(а):
Так компьютеру-то всё равно где точка стоит...
Так там не точка двигается, там длина записи числа полиномиально растет. Если у нас были веса вида $\frac{1}{p_i}$ ($p_i$ - $i$-е простое), то после приведения к общему знаменателю веса могут их логарифмических по размеру входа стать полиномиальными. И это убивает все алгоритмы, работающие за полиномиальное от веса время.

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение16.09.2020, 18:39 


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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение16.09.2020, 23:21 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение17.09.2020, 02:30 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рюкзак с дробным весом предметов
Сообщение26.09.2021, 00:56 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Evgeniy101


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group