динамическое программирование

Как-то вот подход динамического программирования прошел мимо меня. Мне про него запомнилась только статья из "Юного техника", от которого у меня осталось ощущение, что это такой перебор вариантов. Но мне продолжают встречаться упоминания, так что я удосужился наконец-то поинтересоваться.

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

Но это, видимо, более современный подход. В классическом подходе, который видимо и излагался в "Юном Технике", все пространство аргументов сначала упорядочивается каким-то образом, чтобы каждое решение для каждого аргумента могло зависеть только от решений с аргументами, идущими до него в порядке, а потом тупо хреначат и вычисляют лучшие решения для каждого аргумента по порядку, пока не дойдут до заданного.

Если оказывается, что все или почти все аргументы будут так или иначе использованы в рекурсии, то классический подход ничем не хуже рекурсии, а даже наоборот лучше, поскольку не требует глубокого стека. Так что, блин, всего около 30 лет прошло, и achievement unlocked, познал динамическое программирование.

Забавно, кстати, что тот "Юный Техник" вроде как ссылался на Колмогорова, а на самом деле эту хрень изобрел некто Ричард Беллман.

округление

А вот еще к вопросу о динамическом программировании. Одна из типовых задач для него - "заполнение рюкзака".

Когда-то давно, когда я еще учился в школе, мои друзья написали программу для записи кучи файлов с делением на дискеты (файл между дискетами не делится). Это то самое заполнение рюкзаков (дискет). Ну, они лишнего заморачиваться с оптимальностью не стали, а выбирали файлы тупо в порядке "самый большой из оставшихся, который войдет в оставшееся место на дискете".

Но если мы пытаемся использовать динамическое программирование, то оказывается, что все файлы разного размера, и оттого толку от мемоизации - ноль. Чтобы вышел толк, надо округлить размер файлов вверх до некоторого небольшого числа классов. Но тогда очевидным образом решение получается неточным, неоптимальным. Любопытно (не так чтобы очень, а так, выйти потрепаться), есть ли способы легко "добить" такое неточное решение до более точного? Или возникают сильные возмущения и все рушится? Ведь наверняка же кто-нибудь из гигантов мысли уже задавался таким вопросом.