Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2003.01.20;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2003.01.20;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.47 MB
Время: 0.011 c
14-62757
kronprince
2003-01-04 18:13
2003.01.20
Хотел задать очередной наболевший вопрос но передумал :(


14-62783
vJet
2002-12-31 05:27
2003.01.20
SpeechApi


6-62680
NickolayLI
2002-11-13 14:59
2003.01.20
Broadcast


14-62769
uw
2002-12-30 15:59
2003.01.20
Как бы это сделать?


4-62940
Александр Богданов
2002-12-05 07:29
2003.01.20
Опять о выключении компьютера...





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский