Работа со списками чисел...

← →
lionfish (2003-01-09 11:45) [0]

Народ, есть такая проблема:
имеем 2 списка из чисел, длина списков м.б. одинаковой, а м.б. и нет. Например:
72,78,90,100 и 160,200(сумма первого 340, второго 360)
А задача сделать так, чтобы сумма чисел этих списков была одинаковой. Решение выполняется перестановкой чисел из одного списка в другой.
На бумажке всё выглядит довольно просто:
Мы меняем числа 72 и 78 одного списка на число 160 из другого. Сумма каждого списка теперь 350.
А как такое дело можно сделать на дельфи??? Ведь мы можем переставить 3 числа одного списка вместо одного из другого... Возможен вариант, когда вообще невозможно будет точно сравнять их суммы, в таком случае нужно выбрать вариант, которой бы наиболее близко приблизил бы суммы списков к равности...
Вообщем даже не знаю, с какой стороны подступиться...
Возможно, кто-то из вас даст мыслишку... :)

← →
Delirium^.Tremens © (2003-01-09 11:47) [1]

> На бумажке всё выглядит довольно просто:

А бумажку дал "вумный препод"?

← →
Думкин (2003-01-09 11:53) [2]

> Решение выполняется
Ну все правильно - зачем его искать?
1. Суммируешь все и делишь пополам - такие суммы должны быть в каждом столбце. Теперь надо найти комбинации, которые дадут такие суммы - это в тупую, но уже полегче - ничего перставлять не надо.
2. А вообще надо ее привести к виду задачи Линейного программирования. Счас подумаю как.

← →
Reindeer Moss Eater (2003-01-09 11:53) [3]

1.Получить список всех чисел
2.Получить общую сумму.Разделить на два.
3.Отсортировать общий список.
4.Добавлять в первый список числа из общего списка пока сумма в первом списке не превысит половину общей суммы
5 Совершенствовать п.3 и п.4 для наиболее точного решения задачи

← →
Думкин (2003-01-09 12:26) [4]

Ну да - есть вектор из элементов принимающих два значения 1 и -1.
Целевая функция -
модуль( скалярное произведение этого вектора и всех твоих чисел(кои тоже векторе)).
Так вот ее к минимуму. Если минимум 0, то что и искал, еслии не 0, то ближайшше к равенству соответствие.
Списки понятно берутся так
1-й кому +1 соотв, 2-й кому -1 соотв.
Осталось только научится решать такую задачку - учебники по Линейному программированию и вперед.

← →
vlad40 (2003-01-09 12:28) [5]

А разве это задача всегда имеет однозначное решение?

← →
Anatoly Podgoretsky © (2003-01-09 12:30) [6]

Она даже иногда вообще не имеет решиния, не то что однозначного

← →
lionfish (2003-01-09 12:45) [7]

1. Листочек дал "вумный препод" :)
2. Насчёт перебора в тупую: дело в том, что необходимого сочетания может вообще не оказаться. Тогда придётся записывать результаты ВСЕХ переборов, и потом выбирать то, которое ближе к необходимому... Так, допустим мы выбрали наиболее подходящее, каким же тогда образом мы узнаем суммой каких чисел мы получили этот результат... Болт, товарищи.
3. По-моему это невозможно :)

← →
Думкин (2003-01-09 12:50) [8]

Ребята - я все написал.
Да решение возможно не единственно - факт.
Если мнинмум будет 0, то это в точности то, что и просили в самом начале.
Если не 0, то один из вариантов с минимумом разности.
Что еще не понятно?
> Anatoly Podgoretsky © (09.01.03 12:30)
> Она даже иногда вообще не имеет решиния, не то что однозначного

Верно, но автор сам сказал, если нет точного совпадения, то надо минимизировать разность - что и делается.

← →
Думкин (2003-01-09 12:52) [9]

В моей постановке - неизвестное - это вектор с +1 и -1.

← →
Reindeer Moss Eater (2003-01-09 12:55) [10]

Вариация задачи про укладку рюкзака

← →
Думкин (2003-01-09 13:09) [11]

Так ведь наш соотечественник за подобное и Нобеля получил.

Работа со списками чисел... Найти похожие ветки