Главная страница
    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.009 c
3-62430
Max79
2002-12-26 18:28
2003.01.20
Такая проблема: трэба в базу данных запихать HTML, затем читать е


1-62660
Johnny
2003-01-09 22:53
2003.01.20
TImage:вопросик


14-62736
Volly
2002-12-29 12:30
2003.01.20
Оформление как в WinXP


3-62392
Vlad_T
2002-12-24 11:48
2003.01.20
Запрос к двум базам IB


1-62517
БурЖуй
2003-01-10 17:28
2003.01.20
Отмена FormClose





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
Английский Французский Немецкий Итальянский Португальский Русский Испанский