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
11469
damir_777 в сообщении #1483320 писал(а):
Хотел спросить про алгоритм, решающий задачу о неограниченном рюкзаке (Unbounded Knapsack Problem) , но при этом веса предметов являются дробными числами.

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

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


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

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


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

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

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


16/07/14
8355
Цюрих
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
4438
«!!=ВАЖНО=!! Правила выбора раздела для размещения новой темы» [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
5660
Можно попробовать решить задачу по модулю большого простого числа $p$ не делящего ни один из знаменателей.

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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