Куча камней

@Amandosov · Регистрация: 18.11.2012

Author24 — интернет-сервис помощи студентам

Допустим у нас есть камни в количестве n штук и с массамы m_i, где i=1..n, нам надо распределить их в две кучи так, чтобы разниться весов этих кучек было минимальна.

@parsila · 12.02.2014, 18:16

Кажется, что это переформулировка задачи о рюкзаке. Пусть S - сумма весов камней. Возьмем рюкзак вместимостью S/2. Докажем, что наша задача о рюкзаке вместимостью S/2 эквивалентна исходной. Пусть у нас есть две кучки камней и достигнут минимум разности. Тогда в одной из кучек сумма весов камней не больше S/2 - их можно положить в рюкзак. Пусть в рюкзак можно положить больше. Тогда сделаем это и вытащим все из рюкзака в одну кучку, а все, что в рюкзаке не было - во вторую. Получится разность между кучками, меньше, чем исходная. Противоречие. Значит, построенное наполнение рюкзака было оптимальным. В обратную сторону так же.

А задача о рюкзаке решается динамическим программированием, но вообще является NP-полной.

@Amandosov Знаток 156 / 156 / 185 Регистрация: 18.11.2012 Сообщений: 411 Записей в блоге: 2
		1
	Куча камней 11.02.2014, 19:24. Показов 2467. Ответов 1 Метки нет (Все метки) Допустим у нас есть камни в количестве n штук и с массамы m_i, где i=1..n, нам надо распределить их в две кучи так, чтобы разниться весов этих кучек было минимальна. 0

@parsila 5 / 5 / 3 Регистрация: 08.04.2013 Сообщений: 30
	12.02.2014, 18:16	2
	Кажется, что это переформулировка задачи о рюкзаке. Пусть S - сумма весов камней. Возьмем рюкзак вместимостью S/2. Докажем, что наша задача о рюкзаке вместимостью S/2 эквивалентна исходной. Пусть у нас есть две кучки камней и достигнут минимум разности. Тогда в одной из кучек сумма весов камней не больше S/2 - их можно положить в рюкзак. Пусть в рюкзак можно положить больше. Тогда сделаем это и вытащим все из рюкзака в одну кучку, а все, что в рюкзаке не было - во вторую. Получится разность между кучками, меньше, чем исходная. Противоречие. Значит, построенное наполнение рюкзака было оптимальным. В обратную сторону так же. А задача о рюкзаке решается динамическим программированием, но вообще является NP-полной. 0