| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Найти сумму целых чисел с условием минимальной стоимости |
| Автор: FasterHarder 02.12.21, 16:45 |
| Всем хай! Сходу к делу! Есть такая задачка. Дано N (натуральное число, не превышающее 300 000) - количество натуральных чисел в последовательности. Есть только одна операция: взять 2 любых числа и сложить их. Стоимость этой операции равна их сумме. Надо просуммировать все числа (получить скаляр), чтобы стоимость всех операций сложения была минимальной. Пример: N = 5 7 2 11 3 6 1. 2 + 3 = 5 (стоимость = 5) ---> 7 5 11 6 2. 5 + 6 = 11 (cost = 5 + 11 = 16) ---> 7 11 11 3. 7 + 11 = 18 (cost = 16 + 18 = 34) ---> 11 18 4. 11 + 18 = 29 (cost = 34 + 29 = 63) ---> 29 ---> end Ответ: 63 ------------------------- я правильно понимаю, что здесь достаточно брать 2 наименьших числа из текущей последовательности и суммировать их? вроде, да. здесь больше нюансов по структурам данных и алгоритмике обработки, т к отсортировать входную последовательность можно, конечно, но вроде НЕ стоит, т к после суммы сортированность сбивается...хм...Если даже и сортировать, то каким способом. бегать постоянно в циклах, ища 2 мин., тоже вроде слабый вариант. Еще есть вариант - завести доп.массив текущих стоимостей. Просуммировали 2 числа - сумму отправили в этот массив. Очевидно, что тек. стоимость (не общая) на каждом след.шаге возрастает. Затем надо брать не 2 мин.числа из исходного массива, а смотреть на возможные сочетания элементов из исходно массива и массива стоимостей. Но там как-то помечать еще надо, что тек.стоимость использовали и пр. пр. Как-то мутно все это... что здесь самое оптимальное по алгоритму? спс за внимание p.s. это задача с упором на оптимизацию, требуется сверхскоростное решение + мин.объем используемой памяти) |
| Автор: Akina 02.12.21, 17:19 |
| Если действовать "влоб", то в конечной сумме два числа, использованные в первом суммировании, входят в итог 4 раза, во втором - три, в третьем - два, в последнем - 1. Т.е. задача сводится к минимизации функции 4*a(1)+4*a(2)+3*a(3)+2*a(4)+a(5) на заданном наборе чисел (найти минимизирующую перестановку). 1) Берём любую перестановку. Считаем её текущим минимумом. 2) Берём любую перестановку, отличающуюся одной парой (два числа поменены местами). Зная их индексы, легко посчитать изменение итога. Перебираем все перестановки, если ни одна не привела к уменьшению итога - получен ответ, выводим и завершаем. 3) Если же на очередном обмене получено уменьшение итога - фиксируем новое состояние текущего минимума и повторяем пункт 2. Что у функции нет локальных минимумов, доказывать не готов. Цитата FasterHarder @ достаточно брать 2 наименьших числа из текущей последовательности и суммировать их Это "жадный" алгоритм в данном случае. Впрочем, трудно придумать, почему он может дать НЕ оптимум. |
| Автор: FasterHarder 02.12.21, 17:37 |
| Цитата Akina @ Т.е. задача сводится к минимизации функции 4*a(1)+4*a(2)+3*a(3)+2*a(4)+a(5) на заданном наборе чисел (найти минимизирующую перестановку). это интересный подход ВСЕ перестановки?) Длина входной последовательности (макс.случай) = 300 000, вроде по формулам из комбинаторики всего 300 000! перестановок будет) т е это метод ГРУБОЙ СИЛЫ получается? А он точно оптимален по скорости?) Хотя я здесь, скорее всего, не до конца еще понимаю, о каких перестановках говоришь, т к всего предлагаешь менять по 2 элемента, т е их будет гораздо меньше, чем "факториал". Но с др.стороны, ведь есть отличная штука, вот эта: как я понял, а(1) - самый мин, а(2) - 2ой по мин. и пр. Достаточно ТОЛЬКО отсортировать и подставить в эту "функцию" и ответ ГОТОВ. Разве это не лучший способ решения? Единственная трата времени - на сортировку. Ну, можно взять Хоара (qsort) и все. + я вроде хорошо понял этот способ решения (в отличие от перестановок) |
| Автор: Akina 02.12.21, 18:04 |
| Представь, что у тебя есть некое промежуточное ..+12345*a(54321)+12344*a(54322)+.. Обменяем их местами: ..+12345*a(54322)+12346*a(54321)+.. Изменение суммы будет a(54322)-a(54321). Если изначально числа были расположены по возрастанию, то изменение положительно, т.е. такой обмен - затея неудачная. То же для обмена двух не-соседних. Для обмена более чем двух - попробуй сам. Но скорее всего тоже придёшь к выводу, что уйдёшь в минус... хотя не гарантирую. |
| Автор: FasterHarder 02.12.21, 18:15 |
| вот такая программка получилась (за основу взята целевая функция из поста №2): <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> #include <iostream> #include <algorithm> #include <vector> using namespace std; void main(void) { int n; cin >> n; vector<int> numbers(n); for(int i = 0; i < n; i++) cin >> numbers[i]; std::sort(numbers.begin(), numbers.end()); // считаем целевую мин.функцию double cost_total = (n - 1) * numbers[0]; for(int i = 1; i < n; i++) cost_total += (n - i) * numbers[i]; cout << cost_total; cin.get(); } все шикарно работает) у меня лимит по времени 1.5 сек. на выполнение, здесь же, при самой длинной вх.последовательности (300К чисел) работает быстрее секунды (проверил через случ.заполнение rand()). Akina, поклон за эту минимизирующую функцию) Добавлено нашелся тест, на котором программа выдается неправильный результат: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> n = 10 {18, 42, 63, 26, 15, 19, 11, 29, 26, 24} программа выдает 1123, а должно быть 869...причем я не поленился и перепроверил в excel, да, верный ответ 869 (не опечатка) ведать есть какая-то тонкость в этой целевой функции, либо ошибка в коде (хотя код вроде из разряда простых + на остальных тестах были совпадающие ответы)... |
| Автор: scrambrella 02.12.21, 18:51 |
| NP-полная задача о рюкзаке. Найдёте быстрое решение - сделаете революцию. |
| Автор: FasterHarder 02.12.21, 19:13 |
| кажется вкурил, что вот, например на таком ряде: {1, 1, 1, 1, 1, 2, 2, 2, 3} 1 итерация: 1 + 1 = 2 ---> {1, 1, 1, 2, 2, 2, 2, 3} и эта "синяя" минимальная единица ПРОПУСКАЕТ следующие итерации нахождения стоимости... в итоге, наверное, возможен случай, когда в целевой функции вообще не будет ни одного числа, которое встречается в суммах стоимостей (n-1) раз, следовательно, мое предположение, что в функции а(1) - 1ое мин, а(2) - 2ое мин является ошибочным. А если делать полный перебор здесь, то явно за 1.5 сек. не уложится) зы: как всегда все тоньше, нааааааамного тоньше... Добавлено короче, вот правильно считающая программа, правда она умирает по скорости уже от 10К элементов )) для последовательности 300К чисел, думаю, что она "никогда" не посчитает) <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> #include <iostream> #include <algorithm> #include <vector> using namespace std; void main(void) { int n; cin >> n; vector<int> numbers(n); for(int i = 0; i < n; i++) cin >> numbers[i]; std::sort(numbers.begin(), numbers.end()); double cost_total = 0; while(numbers.size() != 1) { double current_sum = numbers[0] + numbers[1]; cost_total += current_sum; numbers.erase(numbers.begin(), numbers.begin() + 2); auto it = std::lower_bound(numbers.begin(), numbers.end(), current_sum); numbers.insert(it, current_sum); } cout << cost_total; cin.get(); } |
| Автор: scrambrella 02.12.21, 21:01 |
| FasterHarder Бросайте уже спортивное программирование. Самостоятельно это не освоить. Есть специальные курсы, где на это натаскивают. У каждого спортсмена есть тренер - бывший или действующий программист-олимпиадник. Вам оно надо? От спортивного программирования до промышленного как пешком до Луны. |
| Автор: AVA12 03.12.21, 12:53 |
| Ну вот зачем в такой простой задаче использовать все эти навороченные вектора, итераторы, курсоры (или что там используется - я не силен в эльфийском). Достаточно обычного массива. Читаем количество элементов N, выделяем массив a[N], заполняем массив, сортируем по возрастанию. Затем в цикле i = 1..(N-1): a[i] += a[i-1] sum += a[i] j := i пока a[j] > a[j+1] && j < (N-1): a[j] <-> a[j+1], j++ |
| Автор: FasterHarder 03.12.21, 15:42 |
| вариант из поста №9 был частично рассмотрен выше, но мне казалось, что сдвиги будут долго выполняться, т к могут продолжаться на много элементов, но, написав эту программу, все отлично по скорости, и 300К за 1.5 сек.вполне рассчитывается. Поэтому, да, этот алгоритм здесь оказался подходящим, признаю AVA12, ну, спс вот программка: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> #include <iostream> #include <algorithm> #include <vector> using namespace std; void main(void) { int n; cin >> n; vector<int> numbers(n); for(int i = 0; i < n; i++) cin >> numbers[i]; //numbers[i] = rand() % 101 - 50; std::sort(numbers.begin(), numbers.end()); double cost_total = 0; for(int i = 1; i < n; i++) { numbers[i] += numbers[i - 1]; cost_total += numbers[i]; int j = i; while((j < (n - 1)) && (numbers[j] > numbers[j + 1])) { std::swap(numbers[j], numbers[j + 1]); j++; } } cout << cost_total; cin.get(); } |
| Автор: scrambrella 04.12.21, 12:01 |
| Цитата FasterHarder @ <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> #include <iostream> #include <algorithm> #include <vector> В олимпиадном программировании любые библиотеки за исключением ввода-вывода запрещены. |