동적 프로그래밍을 사용하여 반복 변환 반복

Question

public static int n; 
    public static int w; 
    public static int[] s; 
    public static int[] p; 

    static void Main(string[] args) 
    { 
     n = 5; 
     w = 5; 

     s = new int[n + 1]; 
     p = new int[n + 1]; 
     Random rnd = new Random(); 

     for (int i = 1; i <= n; i++) 
     { 

      s[i] = rnd.Next(1, 10); 
      p[i] = rnd.Next(1, 10); 
     } 

     Console.WriteLine(F_recursion(n, w)); 
     Console.WriteLine(DP(n, w)); 
    } 

    // recursive approach 
    public static int F_recursion(int n, int w) 
    { 
     if (n == 0 || w == 0) 
      return 0; 
     else if (s[n] > w) 
      return F_recursion(n - 1, w); 
     else 
     {       
      return Math.Max(F_recursion(n - 1, w), (p[n] + F_recursion(n - 1, w - s[n]))); 
     } 
    } 

    // iterative approach 
    public static int DP(int n, int w) 
    { 
     int result = 0; 

     for (int i = 1; i <= n; i++) 
     { 

      if (s[i] > w) 
      { 
       continue; 
      } 
      else 
      {     
       result += p[i]; 
       w = w - s[i]; 
      } 
     } 

     return result; 
    } 

F_recursion 함수를 반복형으로 변환해야합니다. 나는 현재 작동하는 DP가 때때로 작동하지만 항상 그런 것은 아니다. 문제가 F_recursion에 있음을 알게되었습니다. (n - 1, w - s [n]) 반복 솔루션에서 w - s [n]을 올바르게 만드는 방법을 모릅니다. w - s [n] 및 w - s [i]가 w로만 변경되면 프로그램이 항상 작동합니다.

콘솔

:

s[i] = 2 p[i] = 3 
------- 
s[i] = 3 p[i] = 4 
------- 
s[i] = 5 p[i] = 3 
------- 
s[i] = 3 p[i] = 8 
------- 
s[i] = 6 p[i] = 6 
------- 
Recursive:11 
Iteration:7 

그러나 때때로 그것은 작동

s[i] = 5 p[i] = 6 
------- 
s[i] = 8 p[i] = 1 
------- 
s[i] = 3 p[i] = 5 
------- 
s[i] = 3 p[i] = 1 
------- 
s[i] = 7 p[i] = 7 
------- 
Recursive:6 
Iteration:6 

Answer 1

더 큰 숫자가 포함 된 경우 (특히 s의 경우) 다음 접근법이 유용 할 수 있습니다. 결과적으로 2 차원 어레이가 불필요하게 커지지 만 실제로는 결과를 계산하는 데 약간의 w 값만 사용됩니다.

아이디어 : w에서 시작하여 각 i in [n, n-1, ..., 1] 대한 미리 계산 가능한 w 값, w_[i+1] >= s[i] 중복없이 w_[i] 값을 결정한다. i_n을 n 이상으로 반복하고 유효한 w_[i] 값에 대해서만 하위 결과를 계산하십시오.

데이터 저장소로 Dictionary의 배열을 선택했습니다. 이렇게하면 스파 스 데이터를 이렇게 쉽게 디자인 할 수 있기 때문입니다.

public static int DP(int n, int w) 
{ 
    // compute possible w values for each iteration from 0 to n 
    Stack<HashSet<int>> validW = new Stack<HashSet<int>>(); 
    validW.Push(new HashSet<int>() { w }); 
    for (int i = n; i > 0; i--) 
    { 
     HashSet<int> validW_i = new HashSet<int>(); 
     foreach (var prevValid in validW.Peek()) 
     { 
      validW_i.Add(prevValid); 
      if (prevValid >= s[i]) 
      { 
       validW_i.Add(prevValid - s[i]); 
      } 
     } 
     validW.Push(validW_i); 
    } 

    // compute sub-results for all possible n,w values. 
    Dictionary<int, int>[] value = new Dictionary<int,int>[n + 1]; 
    for (int n_i = 0; n_i <= n; n_i++) 
    { 
     value[n_i] = new Dictionary<int, int>(); 
     HashSet<int> validSubtractW_i = validW.Pop(); 
     foreach (var w_j in validSubtractW_i) 
     { 
      if (n_i == 0 || w_j == 0) 
       value[n_i][w_j] = 0; 
      else if (s[n_i] > w_j) 
       value[n_i][w_j] = value[n_i - 1][w_j]; 
      else 
       value[n_i][w_j] = Math.Max(value[n_i - 1][w_j], (p[n_i] + value[n_i - 1][w_j - s[n_i]])); 
     } 
    } 

    return value[n][w]; 
} 

은 일부 공간과 계산이 가능 w의 값을 미리 계산하고 희소 데이터 구조를 지원하기 위해 "낭비되는"것을 이해하는 것이 중요하다. 따라서이 방법은 이 작은 값이 s 인 대용량 데이터 세트의 경우 성능이 좋지 않을 수 있습니다. 대부분 w 값은 하위 결과 일 수 있습니다.

공간이 걱정된다면, 이전 알고리즘을 제외한 모든 결과의 하위 결과를 버릴 수 있습니다.이 알고리즘의 재귀는 엄격한 n-1 패턴을 따르므로이 사실을 알고 있어야합니다. 그러나, 나는 지금 이것을 내 코드에 포함시키지 않을 것이다.

Answer 2

(분명히 하나 개의 변수) 동적 programmig 상태 공간의 서명과 일치하지 않기 때문에 작동하지 않습니다 접근 방식 재귀 적 방법 동적 프로그래밍 접근법의 목표는 상태 공간을 정의하고 채워서 필요한 모든 평가 결과를 사용할 수 있도록해야합니다. 재귀 메서드를 검사 할 때 F_recursion의 재귀 호출은 n 및 w 두 개의 인수를 모두 변경할 수 있습니다. 이는 2 차원 상태 공간이 사용되어야한다는 표시입니다. (명백하게 아이템 속성의 합계 일부 결합 된) 두 번째 인수는 0에서 w 범위 일 수있는 반면 (명백하게 항목의 범위를 제한)

첫 번째 인수는 0에서 n 범위 일 수있다.

당신이 숫자의 숙박하는 이차원 상태 공간

int[,] value = new int[n,w]; 

을 정의한다. 다음으로 값을 undefined로 초기화해야합니다. 값이 다른 최소값이 계산되면 적절한 방식으로 작동하기 때문에 값 Int32.MaxValue을 사용할 수 있습니다.

다음으로, 알고리즘의 반복 버전은 인수를 감소시키는 재귀 적 반복과 달리 전방 방식으로 반복하는 두 개의 루프를 사용합니다.

for (int i = 0; i < n; i++) 
{ 
    for (int j = 0; j < w; j++) 
    { 
     // logic for the recurrence relation goes here 
    } 
} 

가장 안쪽 블록에서 수정 된 버전의 반복 관계를 사용할 수 있습니다. 재귀 호출을 사용하는 대신 value에 저장된 값에 액세스합니다. 값을 반환하는 대신 value에 값을 씁니다.

의미 상 이것은 memoization과 동일하지만 실제 재귀 호출을 사용하는 대신 평가 순서에 따라 필요한 값이 항상 존재하므로 추가 논리가 불필요하다고 주장합니다.

상태 공간이 채워지면 전체 입력에 대한 최대 값을 결정하기 위해 마지막 상태 (즉, 첫 번째 인덱스가 n-1 인 배열의 부분)를 검사해야합니다.