хм, а если в таком случае для i-го веса перебирать все N предметов ?
Не поможет. Проблема в том, что вы не знаете, какие из предметов можно брать для текущего i-ого веса - вдруг они вам очень нужны в конце будут. И просто по одной последней строке вы никак это не определите вообще. И в итоге ваше восстановление ответа может взять один предмет несколько раз, или, если этого избегать, прийти в тупик: все возможные предметы для i-ого веса уже взяты в ответ и что делать вообще непонятно.
Иногда можно прям в массиве хранить множество всех предметов, Но это уже не O(S) памяти. Возможно, это все равно меньше O(SN) для полной матрицы, но не факт.
thirteen_bit, Ну просто перебрать все точки и найти ту, которая дает максимум. Если ищите среди выпуклого множества, то можно бинарным поиском искать - так быстрее, но сложнее.
floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ. В некоторых задачах, как рюкзак без цен с повторениями, действительно, трюк с сокращением таблицы ДП не имеет недостатков.
FlashDok, Ну вот подумайте: если прямоугольник очень высокий, весь луч ни разу не отражается. его длина не зависит от высоты вообще. Если прямоугольник где-то в 2 раза ниже, чем если бы луч был от угла в угол, то луч был бы из двух сегментов. Если их выпрямить - то это будет все тот же прямой луч все той же длины. Т.е. очевино мы можем высоту менять очень в широких пределах не меняя длину.
Если все еще не верите, то в автокаде поиграйтесь с прямоугольником не меняя его длину и угол наклона.
FlashDok, а высота и не учитывается. Если вам надо именно до правой стенки длину подсчитать, то она от высоты не зависит. В более низких прямоугольниках будет просто больше отражений, но длина луча такая же.
FlashDok, где вы ее нашли и что она должна искать? Не подходит. Только первое слагаемое оставьте. Замените еостнус на синус, и если все еще не подходит.
kan3k1k3n, У вас там уже одно целое число. Если же вы хотите, чтобы в файле было "7", то читайте и пишите в текстовом режиме. Открывайте файл с "t" вместо "b" и читайте/пишите fscanf/fprintf, а не fread/fwrite.
Skodio29, да, придется только так. Любая библиотека, что вы откопаете, будет именно так и делать. И это достаточно простой код, чтобы написать его руками.
Xiran, Не влиет, конечно, но если вам нужна переносимость, то используйте, например int32_t. Так-то размер ptrdiff гарантируется быть хотя бы 17 бит, а сколько их там на другой платформе - вы знать не можете.
Скорее всего у вас там где-то Undefinded behavior. Ошибка, короче. Выложите код, чтобы его было удобно читать. Например, кажый файл в отдельный спойлер и в теге code. Или на pastebin. Качать архивы и в них ковырятся ради вас никто не будет.
Adamos, Ох, да. У вас решение за O(n^2) вместо O(n). Это называется "волновой алгоритм". Тоже из теории графов. Для уже упомянутого выше случая
в других вариантах было намного больше этажей
- ваше решение никуда не годится.
Вообще, математическая модель тут - граф. Вы можете сколько угодно отворачиваться от этого факта, но любое ваше решение в итоге будет алгоритмом на графе. Просто если теорию знать, то сразу понятно, какое решение тут хорошее, а какое - не очень. Это как, если вам дано квадратное уравнение, даже если там не x, а количество зайцев и все словами описано, то вы как его не решайте, в итоге все равно получите числа из формулы с дискриминантом.
значит, с рекурсией лучше не рисковать и развернуть ее в цикл.
Там 2 ветки, удачи ее разворачивать.
Но вообще, если, таки, составить математическую модель задачи (граф), то это стандартная задача поиска компоненты связности в графе. Решается или обходом в глубину (типа ваша рекурсия и получается, только стандартно. Понятно почему и как работает и доказано), или обходом в ширину (но это не "развернутая в цикл рекурсия". Это другой подход).
Не поможет. Проблема в том, что вы не знаете, какие из предметов можно брать для текущего i-ого веса - вдруг они вам очень нужны в конце будут. И просто по одной последней строке вы никак это не определите вообще. И в итоге ваше восстановление ответа может взять один предмет несколько раз, или, если этого избегать, прийти в тупик: все возможные предметы для i-ого веса уже взяты в ответ и что делать вообще непонятно.
Иногда можно прям в массиве хранить множество всех предметов, Но это уже не O(S) памяти. Возможно, это все равно меньше O(SN) для полной матрицы, но не факт.