동적 프로그래밍

Question

는, 제 15 장 : 동적 프로그래밍, 나는 동적 프로그래밍 알고리즘을 개발할 때

, 우리는에 따라이 문을 가로 질러왔다 순서는 4 단계 :

1. 최적의 솔루션 구조를 특성화합니다.

2. 최적 해의 값을 재귀 적으로 정의하십시오.

3. 최적의 솔루션 값을 일반적으로 상향식으로 계산하십시오.

4. 계산 된 정보를 사용하여 최적 해를 만듭니다.

단계 1-3은 문제에 대한 동적 프로그래밍 솔루션의 기초를 형성합니다. 에 솔루션 자체가 아닌 최적의 솔루션 값만 필요하면 은 4 단계를 생략 할 수 있습니다. 3 단계에서는 정보를 추가로 유지하기 때문에 최적의 솔루션을 쉽게 구축 할 수 있습니다. 해결책.

I 최적해를 구성 최적해

및

의 값을 계산하는 단계 3과 4

의 차이를 이해하지 않았다.

나는 이것을 더 많이 읽음으로써 이해할 것으로 기대했지만 이해하지 못했습니다. 예를 들어서이 사실을 이해하는 데 도움이 될만한 사람이 있습니까?

Answer 1

우리의 서브 세트가 있는지 여부를 해결하는 동적 프로그래밍을 사용한다고 가정 [1,3,4,6,10]이 3으로 값인 단계 9

대답에 가산 그 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]을 준비하는 중첩 된 for 루프는 사실 3 단계이고 리턴 스테이지의 .reduce() functor는 해시의 마지막 항목 ( hash[tgt])을 형성하여 가장 짧은 결과를 필터링하여 원하는 결과를 얻으므로 4 단계입니다. 목표 값까지 합친 모든 결과 중에서

나에게 2 단계는 다소 의미가 없습니다. 재귀에 대한 언급이 아니라 의미에 의한 표현이기도합니다. 게다가 동적 프로그래밍에 재귀 적 접근법을 사용하거나 본 적이 없습니다. while 또는 for 루프로 구현하는 것이 가장 좋습니다.