Wataru, а ну доказательство, что алгоритм выдаёт неправильный ответ (находит лишние прямоугольники) здесь и так понятно, что чтобы такое было нужно чтобы нвп неравенства неправильно проверяла. Я больше говорил в целом, про подход доказательства, когда оно строится на том, что есть какой то opt (например подпоследовательность) и алгоритм не может её пропустить, а значит обязательно найдёт
ну а если можно переворачивать то вроде достаточно отсортировать ещё этим k измерениям каждый объект и рассматривать конкретный поворот k мерного прямоугольника с отсортированными координатами как здесь, например
если для k измерений, то в общем случае тут сортировка (за k * n * logn) нужна просто для того, чтобы сделать перед НПВ (по k параметрам) правильный относительный порядок элементов, чтобы НВП этим пользоваться могла и перебирать только предыдущие элементы
а почему недостаточно того, что у оптимальной последовательности сохранится относительный порядок в отсортированном массиве, а значит её обязательно найдёт НВП ?
Alexandroppolus, вот как раз оптимальность оно и обосновывает потому что если именно таким образом отсортировать массив, то относительный порядок элементов оптимальной последовательности будет правильным (таким же как в отсортированном массиве), а значит после её найдёт НВП
Но я больше спрашивал про абстрактный подход, а не про конкретную задачу
floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ
хм, а если в таком случае для i-го веса перебирать все N предметов ? тогда правда в отличие от 2-D динамики сложность восстановления ответа будет не S, а N * S
для одномерного массива вроде всё ок восстанавливается
d[i] = bool хранится, можно ли получить вес = i
ну и для восстановления ответа, находясь на j-м предмете, в позиции i проверяем, есть ли ребро (dp[i - item[j].weight] == true) используя j-й предмет, если есть то добавляем в ответ, и идём к j-1 предмету
Хм, может я что-то не так понял, но я имел в виду, что в исходном решении плотность распределения равномерная - φ∊[0, π] f(φ) = 1/π.
А что делать, если, например, φ∊[0, π] f(φ) = (1/S) * √φ, где 1/S - коэф. нормировки (S площадь под кривой от 0 до π), ну то есть значения π из интервала [0, π] неравномевроятны
Хотя я сейчас сонный, мог что-то не догнать :)
