Имеется набор значений весовых коэффициентов и набор значений, составленных из этих весовых коэффициентов.

Например:
Значения - 12 32 34 65 76 123
Значения весовые коэффициенты – 1 2 3

Задача – максимально выровнять значения между собой, манипулируя весовыми коэффициентами так, что если у какого-то значения весовой коэффициент убирается/вычитается, то он должен быть обязательно присоединён (прибавлен) к другому значению. Т.е., т.о., сумма значений при любых манипуляциях не должна меняться.

P.S. На всякий случай: задача решается на С++.

Это сообщение отредактировал(а) Rutti - 26.12.2006, 12:36

Ох. Среднее арифметическое с последующим прибавлением/вычитанием дробных частей...
Даже коэффициенты 2 и 3 не нужны.

"P.S. На всякий случай: задача решается на С++.
"


На все всякие случае - задача является вычислимой по Тьюрингу функцией

Можно популярно? Знаю машину Тьюринга, но функцию впервые слышу...
Или просто я тупой или ты написал "Юзай поиск"?

Модератор: 
[тихонько так], может, обсудить это где-то ещё?  
(это я касательно машины Тьюринга)

Это сообщение отредактировал(а) maxim1000 - 26.12.2006, 17:42

Ок. Решение я привел. Среднее арифметическое, а там уже доделываем до целых чисел, если надо.
Хотя задача должна ставиться так: найти максимально короткую последовательность операций, в результате которой мы макимально уравняем последовательность.
Но такую задачу не ставили 

Я прошу прощения за не совсем корректно поставленную задачу. Дополняю.

Каждый элемент Значений "привязан" к определённым весовым коэффициентам (т.е., например, первый элемент Значений - 12, был создан только весовыми коэффициентами 1 и 3). И, поэтому, при уравнивании последовательности к каждому элементу Значений могут быть применимы только "создавшие" его весовые коэффициенты.

Берешь и раскладываешь каждую твою цифру на составляющие, из которых она "сделана".
Складываешь тройки в одну кучу, двойки- в другую. Угадай, куда единицы 
Затем раскладываешь эти кучи равномерно по количеству цифр в начальной последовательности.
Т.е. у нас допустим есть пять троек, две двойки и шесть единиц.
Надо создать последовательность из 4 элементов.
Получаем
3 3
3 2
3 1 1 1
3 1 1 1
Каждый столбик соответствует номеру прохода. Первый- положили тройки, далее по убыванию...
ИМХО проще уже не объяснить...

В таком случае внесу ещё одно уточнение.
Фиксировать количество "составляющих" совсем не хочется.
Хотелось бы получить решение задачи исходя из того, что не известно сколько определённых "весовых коэффициентов" использовалось при составлении каждого Значения.

ооох. Что с тобой делать, а?
Ну и что, что неизвестно?
Тебе алгоритм разложения еще написать, а?
Все то же самое, только в обратную сторону.
Можно вычесть тройку из каждого числа? Вычитаем. Ага. Уже нельзя. Вычитаем двойку. Придумываем критерий равновесности для разложения. И так далее