Форум программистов, компьютерный форум, киберфорум
Наши страницы

Организовать перебор всех возможных сочетаний - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Работа с матрицей. Сравнение строк и столбцов http://www.cyberforum.ru/cpp-beginners/thread1184087.html
Здравствуйте. Помогите пожалуйста реализовать сравнение каждой строки со всеми столбцами. Предположим есть матрица 3х3: 3 0 2 1 6 0 0 4 0 нужно сравнить...
C++ Бинарный поиск для char Здравствуйте, сделал программу для поиска заглавных и строчных букв в вводимом с клавиатуры тексте. Ищет отлично и без проблем, но нужно сделать еще бинарный поиск. Вводимую строку сортирует,... http://www.cyberforum.ru/cpp-beginners/thread1184084.html
Вывести числа, которые почти равны друг другу (их разность меньше 0,01) C++
Здравствуйте. Занимаюсь С++ по книге Бьерна Страуструпа. Помогите решить задачу: Напишите программу, содержащую вектор и цикл while, которая выводит числа, которые почти равны друг другу(их разность...
Непонятная причина вылета программы C++
Добрый день, была поставлена задача написать программку, которая бы высчитывала кол-во повторений в массиве, а затем бы выводила минимальный и максимальный элемент массива, все требовалось...
C++ Прочитать файл scanf http://www.cyberforum.ru/cpp-beginners/thread1184043.html
Текстовый файл имеет следующее содержание: число, пробел, слово, пробел, число; и состоит из неизвестного кол-ва строк. Как прочитать файл и занести в структуру? struct Str { int Numb; char...
C++ Вывод символов в привычной форме При запуске программы в Dev c++ все символы отображаются не в виде русского или английского текста,а в виде непонятных символов( видимо стандартная кодировка в виндовс). Как сделать так,чтобы всё... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.05.2014, 20:26
Сформулировал-таки доказательство:

Пусть R – оптимальное разбиение множества S на пары, т.е. пара его элементов (m, M) с максимальной суммой имеет минимально возможное значение этой суммы.
Добавим к R еще пару (n, N) элементов таких, что в отсортированном массиве значений элементов они стоят на концах.
Докажем, что новое разбиение R1, состоящее из R и пары (n, N), также является оптимальным.
а) Пусть n + N >= m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше n + N.
Действительно, если такое разбиение существует, то в нем нет пары (n, N), т.е. элемент N там сочетается с неким элементом k. Но элемент n самый левый, следовательно n <= k и n + N <= k + N, т.е. максимальная сумма пары в этом разбиении не меньше n + N.
б) Пусть n + N < m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше m + M.
Предположим, что такое разбиение существует.
1) Пусть в этом разбиении присутствует пара (n, N).
Тогда, удалив ее, мы получим разбиение множества S с максимальной сумой пары меньше, чем m + M, что противоречит условию.
2) Пусть в этом разбиении отсутствует пара (n, N).
Тогда элемент n сочетается с неким элементом B из множества S. Но элемент N самый правый, следовательно B <= N. Удалив из разбиения пару (n, B), мы получим разбиение R2 множества S, в котором элемент B заменен на не меньший элемент N, но при этом максимальная сумма пары (m1, M1) меньше, чем m + M. Заменим в разбиении R2 элемент N обратно на B. Мы получим разбиение множества S, в котором сумма каждой пары не больше m1 + M1, т.е. меньше m + M, что противоречит условию.
Из вышедоказанного следует, что разбиение множества значений на пары, элементы которых равноотстоят от концов отсортированного массива значений, является оптимальным.
3
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru