Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Amandosov
Знаток
156 / 156 / 185
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
1

Куча камней

11.02.2014, 19:24. Просмотров 1556. Ответов 1
Метки нет (Все метки)

Допустим у нас есть камни в количестве n штук и с массамы mi, где i=1..n, нам надо распределить их в две кучи так, чтобы разниться весов этих кучек было минимальна.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2014, 19:24
Ответы с готовыми решениями:

с помощью камней уравновесить весы
Дано: В файле даётся информация о камнях. До 5000 камней. По каждому камню даётся вес в граммах....

Структура данных куча
Следует ли делать индексатор на чтение/запись для изменения элементов кучи напрямую?

Куча сложность доступа к элементам
Добрый день! Сломал голову, не могу определиться. Какая алгоритмическая сложность доступа к...

Куча камней
У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит...

Куча камней
Добрый день! Пытаюсь решить задачу на java, условие и решение которой представлено ниже. Дело в...

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

А задача о рюкзаке решается динамическим программированием, но вообще является NP-полной.
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2014, 18:16

Имеется одна куча камней
Имеется одна куча камней. Известна масса каждого камня. Разделить эту кучу на две, чтобы массы...

Простенькая задачка из Timus Online Judge(1005. Куча камней)
Собственно условие: http://acm.timus.ru/problem.aspx?space=1&num=1005 Моё решение: #include...

Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь
Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.