Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina,

Для чего собственно и нужен массив текущих местоположений гирь.

Что значит текущих положений гирь? Такое текущее положение может быть в переборе, где у вас одно состояние рассматривается в каждый момент времени и чуть чуть туда-сюда меняется. Если у вас ДП, то у вас куча состояний и для каждого из них есть "местоположение гирь".

Если стостояние {сколько гирек обработали, сколько весит первая кучка, сколько весит вторая кучка} (как у автора вопроса), то достаточно хранить одно только число - в какой кучке лежит последняя из обработанных гирек. Чтобы восстановить все гири, надо эту последнюю выкинуть из рассмотрения, вычев ее из нужной кучки и повторить операцию уже в новом состоянии. Именно это описанно у меня в ответе ниже.

Но там все-равно есть трехмерный массив для всех стостояний.

Или вы предлагаете сделать его четырехмерным и хранить еще для каждой гирьки, где она лежит - куб из "текущих местоположений гирек"?

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Это перебор и получается же. Хоть и не такой наивный. Вариантов набить первый рюкзак экспоненциально много. Вам надо для каждого попытаться потом набить второй рюкзак. В худшем случае - вы переберете их все, если решения для обоих рюкзаков нет.

Тут есть только одно быстрое решение - набивать оба рюкзака сразу, включив в стостояние ДП текущий вес в обоих рюкзаках.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, Тогда вам нужно что-то вроде reservoir sampling. Гуглите. На каждом этапе вероятность взять текущий элемент зависит от того, сколько у вас элементов осталость и сколько еще надо взять.

int taken = 0;
for (int i = 0; i < n; ++i) {
  if (rand()*(n-i) < k-taken) {
    ++taken;
    // Взять элемент i.
  }
}

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Нет, без двумерного массива вы не восстановите ответ. (трюк с одномерной плоской индексацией и расправлением многомерного массива в одномерный не считается).

Всё равно ж надо начинать с подсчёта общего веса и проверки, что оно вообще возможно, а также расчёта веса каждой кучки. А потом, используя ДП, набиваем один рюкзак, а по завершении второй.

Целевой вес каждого рюкзака известен - общая сумма весов / 3.

Нельзя набивать рюкзаки по очереди. Вы можете найти решение для первого рюкзака такое, что никак не получится набить второй оставшимеся объектами. Например у вас веса {1, 3, 2, 2, 1, 3}. Если вы случайно в первый рюкзак возьмете {1,1,2}, то уже никак из оставшихся {2,3,3} вы второй рюкзак размера 4 не наберете.

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Нет, при таких маленьких весах и таком огромном количестве гирек - это задача на Динамическое Программирование. Ибо перебор тут будет из 3^60 вариантов - не дождетесь до смерти солнечной системы, а ДП тут 60*(1200)^2 = 60^5 = 86400000 операций - отработает за доли секунды. Даже если вы всякие хитрые отечения вроде ветвей и границ будете использовать - вы в ограничения по времени не уложитесь.

Ну и, там прямо на сайте наиписано

ДП: Условия задач

Когда передавать копию callable, а когда через rvalue reference?

Dyikot, а каких? Конкретнее пожалуйста.

Когда передавать копию callable, а когда через rvalue reference?

Пример бы кода, что у вас за библиотеки и как используются.

Вообше, callable может быть большим объектом из-за всяких связанных аргументов функции. Поэтому лучше его не копировать. Но, и перемещать его не всегда можно, ведь он может быть нужен потом опять.

В чем суть логической ошибки, продемонстрированной в старинном учебнике?

Rsa97,

Откуда вам известно, что существует прямоугольный треугольник со сторонами 3, 4 и 5?

По построению, например. Берем прямоугольный треугольник с двумя катетами 3 и 4. По теоремме пифагора получам гиппотенузу 5.

Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

lex899, Лень возиться, этот спор того не стоит. O(n!) - медленное решение. O(n) - оптимальное. Ваша реализация на 35% быстрее за счет микрооптимизаций, но от этого не единственно верная, особенно в контексте обучающей задачки (иначе бы не было этих странных ограничений на вложенные циклы)

Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

lex899, А если на каких-нибудь векторных интринсиках переписать, то еще быстрее будет. При чем аж в несколько раз! Значит ли это, ваше решение неправильное?

Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

lex899,

в задачах где по условиям будет ограничено время/память данное решение не доберет по баллам,

Я занимался олимпиадами много лет, брал призы на чемпионатах мира, так что могу на личном опыте сказать, что в 99.999% случаев никого вылизывания кода для ускорения не делается. Достаточно оптимальный алгоритм выбрать.

Современные процессоры настолько непредсказуменые, поэтому тайм лимиты подбираются с большим запасом.

Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

lex899,

Да, вы правы, что код в вопросе можно соптимизировать. Но нет, этого делать не обязательно. Это какие-то жалкие проценты.

но 4 цикла дороже одного, умножение дороже

Там совсем небольшая разница по сравнению с одним циклом, ведь тело цикла никуда не исчезает, а лишь разбивается по нескольким циклам. Это тело цикла полно непредсказуемых ветвлений и практически вся работа именно там и происходит. "Лишние" циклы добавляют лишь по одному инкрименту и одному абсолютно предсказываемому ветвелению на сам for. Это по сравнению с основной работой не много. В самом патологическом случае вы в теоретически лишь в 2 раза медленнее сделаете программу. На практике этого не досчтичь, даже для очень простых циклов, ибо маленькие тела циклов компилятору легче оптимизировать, разворачивать, инлайнить туда функции, использовать регистры и т.д. Так что на практике код с несколькими циклами может даже оказаться быстрее.

умножение дороже и несет риск переполнения

Умножение целых почти такое же быстрое, как и сложение. По сравнению с работой с памятью и вводом - это копейки. Умножение все-равно делать в итоге надо по условию задачи и там нет переполнения.

но навскидку выглядит как набор антипаттернов.

Если вам не надо выжать последние проценты производительнсоти из вашего процессора, то как раз схлопывание всего в один цикл будет антипатерном, потому что такой код сложнее читать, легче там накосячить и тяжелее его изменять. Это те самые преждевременные оптимизации, которые являются злом по известной цитате Дональда Кнута.

Даже на олимпиадах практически никогда не требуется микрооптимизаций, если у вас правильная временная сложность алгоритма.

Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

lex899, Да, такое решение правильное. Возможно там будет чуть меньше кода, чем в решении автора вопроса, но оно такое же по временной сложности. Более того, решение в вопросе фактически то же самое и делает, только отдельным циклом для каждого из 4 чисел. И вместо поиска второго минимума, ищется число, которое даст максимум произведения с минимумом, что окажется вторым минимумом как раз, если первый был отрицателен.

Покажите на ассемблере как выглядит защита от переполнения буфера?

Rsa97, Sasha_88, Во-первых, библиотечный код, особенно at, компилятор инлайнит почти всегда и его видно. Там cmp, jmp и call __throw_out_of_range_fmt.

Во-вторых, если хочется посмотреть, что там в стандартной библиотеке, можно локально на своем компьютере скомпилировать со статической линковкой, дизассемблировать и посмотреть на весь файл.

Да в том же дебаггере можно запустить программу и зайти внутрь vector::at - можно будет и исходники проверок посмотреть, да и ассемблерный код.

Покажите на ассемблере как выглядит защита от переполнения буфера?

Sasha_88, надо видеть, так посмотрите на https://godbolt.org/

Пишите ваш код, выставляйте флаги компилятора и смотрите ассемблерный выход.

Ошибки winsock 10054 и 10053. Как решить?

gethighlikeplanes, Т.е. проблема была только в порте?

Ошибки winsock 10054 и 10053. Как решить?

gethighlikeplanes, Добавьте побольше вывода в оба клиента, а тоу вас не видно, что и когда отправляется.

Ошибка редкая и странная. Система разрывает соединение, потому что что-то сломалось. Кончилось место в буфере, keep-alive не проходят и т.д.

Возможно фаервол или антивирус что-то бокируют?
Или какие-то разные потоки пытаются что-то одновременно сделать с сокетами?

Ошибки winsock 10054 и 10053. Как решить?

gethighlikeplanes, У вас оба пира делают recv? Или это ошибка в отладочном выводе?

Ошибки winsock 10054 и 10053. Как решить?

Попробуйте file_size на обоих концах выводить на экран. И вообще отладочного вывода вставить побольше. Оно падает сразу же, или часть файла отправяет/передает?

Ошибки winsock 10054 и 10053. Как решить?

Оберните код в тег code (кнопка </> в редакторе). Иначе вопрос удалят.