Динамическое программирование из книги CORMEN игровая

Question

При чтении о динамическом программировании в «Введение в алгоритмы» По Cormen, Глава 15: Динамическое программирование, я наткнулся на это заявление

При разработке алгоритма динамического программирования, мы следуем последовательность четыре этапа:

1. Охарактеризуйте структуру оптимального решения.

2. Рекурсивно определить значение оптимального решения.

3. Вычислить значение оптимального решения, как правило, снизу вверх.

4. Построить оптимальное решение из вычисленной информации.

Этапы 1-3 составляют основу решения динамического программирования проблемы. Если нужно только значение оптимального решения, а не само решение, то может опустить шаг 4. Когда мы выполняем шаг 4, мы иногда поддерживаем дополнительную информацию на этапе 3, чтобы мы могли легко построить оптимальное решение.

я не понял разницы в шаге 3 и 4.

вычисления значения оптимального решения

и

построения оптимального решения.

Я ожидал понять это, прочитав еще больше, но не понял. Может ли кто-нибудь помочь мне понять это, представив пример?

Answer 1

Предположим, что мы используем динамического программирования для работы, есть ли подмножество [1,3,4,6,10], который суммирует до 9.

Ответ на шаг 3 это значение, в этом case "TRUE".

Ответ на шаг 4 составляет фактическое подмножество, суммируемое до 9, в данном случае «3 + 6».

Answer 2

В динамическом программировании мы в большинстве случаев получаем огромный хэш результатов. Однако изначально он содержит только результат, полученный из первого, самого маленького, простейшего (нижнего) случая и, используя эти начальные результаты и вычисляя сверху, мы в конечном счете сливаемся с целью. На данный момент последний элемент в хэше большую часть времени является целью (шаг 3 завершен). Затем нам придется обработать его, чтобы получить желаемый результат.

Прекрасным примером может быть поиск минимального количества кубов, суммирующих до цели. Цель - 500, и мы должны получить [5,5,5,5], или если цель равна 432, мы должны получить [6,6].

Таким образом, мы можем реализовать эту задачу в JS следующим образом:

function getMinimumCubes(tgt){ 
 
    var maxi = Math.floor(Math.fround(Math.pow(tgt,1/3))), 
 
     hash = {0:[[]]}, 
 
     cube = 0; 
 
    for (var i = 1; i <= maxi; i++){ 
 
    cube = i*i*i; 
 
    for (var j = 0; j <= tgt - cube; j++){ 
 
     hash[j+cube] = hash[j+cube] ? hash[j+cube].concat(hash[j].map(e => e.concat(i))) 
 
            : hash[j].map(e => e.concat(i)); 
 
    } 
 
    } 
 
    return hash[tgt].reduce((p,c) => p.length < c.length ? p:c); 
 
} 
 

 
var target = 432, 
 
    result = []; 
 
console.time("perf:"); 
 
result = getMinimumCubes(target); 
 
console.timeEnd("perf:"); 
 
console.log(result);

Таким образом, в этом коде hash = {0:[[]]}, это шаг 1; вложенные для петель, которые в конечном итоге готовят hash[tgt], фактически являются этапом 3, а функтор .reduce() на этапе возврата является этапом 4, поскольку он формирует последний элемент хэша (hash[tgt]), чтобы дать нам желаемый результат, отфильтровав самый короткий результат среди всех результатов, суммирующих до целевого значения.

Для меня шаг 2 несколько бессмыслен. Не из-за упоминания о рекурсии, но и по смыслу. Кроме того, я никогда не использовал и не видел рекурсивного подхода в динамическом программировании. Он лучше всего реализуется с помощью петель while или for.