Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Работа со списками чисел... [D5, Win95/98, WinXP]

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

Думкин (2003-01-09 13:09:00) [1]
Так ведь наш соотечественник за подобное и Нобеля получил.

Reindeer Moss Eater (2003-01-09 12:55:00) [2]
Вариация задачи про укладку рюкзака

Думкин (2003-01-09 12:52:00) [3]
В моей постановке - неизвестное - это вектор с +1 и -1.

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

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

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

Anatoly Podgoretsky (2003-01-09 12:30:00) [6]
Она даже иногда вообще не имеет решиния, не то что однозначного

vlad40 (2003-01-09 12:28:00) [7]
А разве это задача всегда имеет однозначное решение?

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

Думкин (2003-01-09 11:53:00) [9]
> Решение выполняется
Ну все правильно - зачем его искать?
1. Суммируешь все и делишь пополам - такие суммы должны быть в каждом столбце. Теперь надо найти комбинации, которые дадут такие суммы - это в тупую, но уже полегче - ничего перставлять не надо.
2. А вообще надо ее привести к виду задачи Линейного программирования. Счас подумаю как.

Reindeer Moss Eater (2003-01-09 11:53:00) [10]
1.Получить список всех чисел
2.Получить общую сумму.Разделить на два.
3.Отсортировать общий список.
4.Добавлять в первый список числа из общего списка пока сумма в первом списке не превысит половину общей суммы
5 Совершенствовать п.3 и п.4 для наиболее точного решения задачи

Delirium^.Tremens (2003-01-09 11:47:00) [11]

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

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

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »