Форум программистов, компьютерный форум CyberForum.ru

Максимальная сума - C++

Восстановить пароль Регистрация
 
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
10.10.2010, 15:24     Максимальная сума #1
Есть пары чисел А и В:
2 -- 37
3 -- 45
1 -- 46
4 -- 30

Они задают матрицу следующим образом(картинко 1.)
Нужно выбрать такие числа, чтобы их сума была наибольшей
(Числа должны быть на разных вертикалях и горизонталях)
в примере сума = 232
Миниатюры
Максимальная сума  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2010, 15:24     Максимальная сума
Посмотрите здесь:

C++ Сума значений Функции
сума ряда C++
Сума цифр веденного числа N C++
C++ Сума четных елементов и т.д.
Сумма цифр натурального числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
10.10.2010, 19:09  [ТС]     Максимальная сума #2
кроме перебора в голову больше ничего не приходить, а пар чисел может быть до 30 шт.
тоесть общая сложность 30! (30 факториал)

Добавлено через 3 часа 43 минуты
если выбирать в каждом столбце максимальный елемент - не всегда сума получается наибольшей
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
10.10.2010, 20:12     Максимальная сума #3
Mayonez, а откуда задачка? не из транспортной задачи?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2010, 07:54     Максимальная сума #4
PointsEqual, Это из задачи: http://www.e-olimp.com/problems/6

Mayonez,
Матрица будет иметь максимальный размер 14*14 (потому что максимальное число путевок - 14 мы всегда сможем продать за первые 14 дней).
Сформировать такую матрицу очень просто. Остается только выбрать в каждом столбце (и каждой строке) по 1 числу, что бы сумма этих чисел была максимальная. Рекурсия (перебор) здесь проходит по времени.
Yandex
Объявления
21.12.2010, 07:54     Максимальная сума
Ответ Создать тему
Опции темы

Текущее время: 09:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru