2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача о монетах
Сообщение18.11.2014, 20:51 


10/05/13
251
У нас есть мешок из $N (1 \le N \le 100)$ монет. Достоинство монеты это натуральное число не большее $500$.
Надо найти минимальную разницу двух куч, на которые будут разделены монеты. Единственную монету делить нельзя.
Я отнес задачу к задачам динамического программирования.

Пробую решить:
Отсортируем массив $a$ по неубыванию.
$DP[1]=a[1]$
$DP[2]=a[2]-a[1]$
$DP[3]=a[3]-(a[2]+a[1])$

Если писать дальше - мое решение сводится к перебору.

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 21:00 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Я бы нашёл общую стоимость мешка, поделил на два потом стал решать задачу набора максимально близкой снизу к этому числу суммы имеющимися монетами. Такие алгоритмы есть.

+++ Надеюсь, я правильно понял, что под "будут разделены" понимается "все монеты могут быть разделены".

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 21:04 


10/05/13
251
Да, крутая идея!

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 21:23 


05/08/08
55
Санкт-Петербург
Максимально близкое значение, меньшее A, - это укладка рюкзака. Алгоритмы, конечно же, есть, но это все равно перебор, причем NP-трудный.

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 21:23 


10/05/13
251
gris в сообщении #933023 писал(а):
+++ Надеюсь, я правильно понял, что под "будут разделены" понимается "все монеты могут быть разделены".

Монет самих делить нельзя, можно просто перекидывать монету с кучи на другую.
А вот задача к которой вы свели ее, поиск наиболее близкого снизу, можете дать ссылки на метод ее решения?

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 21:28 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
frankenstein,
kknop в сообщении #933037 писал(а):
Максимально близкое значение, меньшее A, - это укладка рюкзака.
Это термин. По нему и ищите.То есть "задача о рюкзаке". Иногда называют "задача о ранце".

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение18.11.2014, 22:00 
Заслуженный участник
Аватара пользователя


13/08/08
14495
frankenstein, у Вас даже упрощённая задача, так как "веса" монет равны и не учитываются. Но при количестве 100 монет полный перебор организовать не удастся за разумное время, как и гарантированно получить точное решение. Разных алгоритмов много и они отличаются по требованиям, по априорным характеристикам ценностей и т.д. Ссылки, наверное, общедоступны, но я хороших не знаю :cry:

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение19.11.2014, 02:34 
Заслуженный участник


16/02/13
4214
Владивосток
Смею вас уверить, такую задачу я решал в эпоху XT на Клиппере. С парой эвристик пролетало со свистом, и 100, и 1000.

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение19.11.2014, 10:02 


10/05/13
251
iifat в сообщении #933169 писал(а):
Смею вас уверить, такую задачу я решал в эпоху XT на Клиппере. С парой эвристик пролетало со свистом, и 100, и 1000.

Укладывалось за полсекунды? :mrgreen:

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


13/08/08
14495
Эта задача в той или иной форме распространена на практике. И чаще всего никто не ищет точного решения, которое и не достижимо, так как обычно стоимости, веса и другие характеристики объектов заданы с погрешностями. И вполне достаточны, например, рекомендации по размещению наиболее "громоздких" объектов. В былые годы и на Феликсе за десять минут управлялись.
Но бывают и чисто теоретические задачи, когда необходимо получить именно точное решение, причём все. Вам надо определиться с целями написания алгоритма. Если цель — сам Алгоритм, всемогущий и молниеносный, то она очень благородна, но трудна.

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение19.11.2014, 13:49 


10/05/13
251
Меня интересует применение алгоритма на олимпиадах, а там традиционно надо, чтобы алгоритм уложился за несколько секунд.
Нашел решение, всем огромное спасибо.
Эта задача оказалась частным случаем задачи о рюкзаке, в котором вес совпадает со стоимостью, ее оказывается называют
задачей о сумме подмножеств.

Если хотите порешать задачу http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=503&mosmsg=Submission+received+with+ID+14553083

 Профиль  
                  
 
 Re: Задача о монетах
Сообщение19.11.2014, 14:10 
Заслуженный участник


16/02/13
4214
Владивосток
frankenstein в сообщении #933249 писал(а):
Укладывалось за полсекунды?
По-разному. Я разбивал zip-архив по дискетам. Максимум, по-моему, подсовывал архив на пять не то десять дискет, что-то около тысячи файлов. Часами у компа не сидел.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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