Задача о монетах

[frankenstein]

У нас есть мешок из $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])$

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

[gris]

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

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

[frankenstein]

Да, крутая идея!

[kknop]

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

[frankenstein]

gris в сообщении #933023 писал(а):

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

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

[provincialka]

frankenstein,

kknop в сообщении #933037 писал(а):

Максимально близкое значение, меньшее A, - это укладка рюкзака.

Это термин. По нему и ищите.То есть "задача о рюкзаке". Иногда называют "задача о ранце".

[gris]

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

[iifat]

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

[frankenstein]

iifat в сообщении #933169 писал(а):

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

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

[gris]

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

[frankenstein]

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

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

[iifat]

frankenstein в сообщении #933249 писал(а):

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

По-разному. Я разбивал zip-архив по дискетам. Максимум, по-моему, подсовывал архив на пять не то десять дискет, что-то около тысячи файлов. Часами у компа не сидел.