Как лучше восстановить индексы в 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 (кнопка </> в редакторе). Иначе вопрос удалят.

Как называется такая структура данных?

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

Как называется такая структура данных?

historydev, Ну тогда это решение вполне оправдано. Но названия у него особого нет. Может быть, Хеш-таблица с кешем для итерации. В каких-то языках в стандартных библиотеках хеш-таблицы, скорее всего, прямо так и реализованы. Ибо хранить толстые объекты прямо в слабо заполненной таблице дорого. Там хранят указатели, или индексы, а сами элементы лежат где-то рядом в массиве.

Почему без std::remove_reference_t не работает?

А что за шаблон Cfunc?

Вообще, не вижу противоречия. У вас же там tfunc&&, его вы пытаетесь к void* привести и к нему применяете remove reference.

Попробуйте в ваш static assert добавить std::move.