동적 프로그래밍을 사용하여 배낭에서 항목 검색

Question

동적 프로그래밍이 생소하고 처음으로 DP 문제를 시도했습니다. 문제는 성명서는

크기가 n이고 크기가 []이고 값이 [] 인 배낭이 배낭에 넣을 수있는 항목의 용량을 최대화합니다. 항목은 여러 번 반복 될 수 있습니다. (중복 된 항목이 허용됨).

내가 재발 관계를 수립하고, DP 테이블을 만들고, 결국 배낭에 넣어 수있는 최대 값을 얻을 수 있었지만

, 나는 장치로해야하는 값을 검색하는 방법 수 없습니다입니다 필요한 합계를 얻기 위해 선택되었습니다.

여기 내 솔루션입니다 : 내 솔루션에서

#include <iostream> 
#include <cstdlib> 
#include <algorithm> 
#include <vector> 

using namespace std; 

int main() 
{ 
    int s[] = { 1, 3, 4, 5, 2, 7, 8 , 10}; 
    int v[] = { 34, 45, 23, 78, 33, 5, 7 , 1}; 
    int n = ((sizeof(s))/(sizeof(s[0]))); 
    vector<int> backtrack; 
    int C = 15; 
    int pos; 
    int m[20]; 
    m[0] = 0; 
    int mx = 0; 
    for (int j = 1; j <= C; j++) { 
     mx = 0; 
     m[j] = m[j-1]; 
     pos = j-1; 
     for (int i = 0; i < n; i++) { 
      mx = m[i-s[i]] + v[i]; 
      if (mx > m[i]) { 
       m[i] = mx; 
       pos = i - s[j]; 
      } 
     } 
     backtrack.push_back(pos); 
    } 
    cout << m[C] << endl<<endl; 
    for (int i = 0; i < backtrack.size(); i++) { 
     cout << s[backtrack[i]] <<endl; 
    } 
    return 0; 
} 

, I는 벡터에 selcted 최대 값 항목의 위치를 ​​저장하고, 결국 그들을 인쇄하려고 시도했습니다. 그러나 이것은 나에게 정확한 해결책을주지 않는 것 같습니다.

프로그램을 실행하면 생성합니다

79 

2 
3 
0 
5 
2 
7 
8 
10 
34 
45 
23 
78 
33 
5 
7 

그것은 출력의 숫자가 출력에 표시되는 항목의 크기가 같은 크기 0의 어떤 항목이 선택되지 못할 출력에서 ​​분명하다.

내 논리 또는 구현에서 오류를 찾는데 도움이되기를 바랍니다. 감사.

Answer 1

당신은 욕심 많은 접근 방식을 따르고 있습니다. 꽤 똑똑하지만 경험적입니다. 그것은 숙제 수 있습니다 나는 당신에게 올바른 코드를 제공하지 않습니다,하지만 재귀 함수 knapsack는 다음과 같이 보일 것이다 :

코드에서

knapsack(C): maximum profit achivable using a knapsack of Capacity C 
knapsack(C) = max { knapsack(C-w[i]) + v[i] } for all w[i] <= C 
knapsack(0) = 0 

: PeeWee2201 @

dp(0) = 0; 
for i = 1 to C 
    dp(i) = -INF; 
    for k = i-1 downto 0 
    if w[k] < i then 
     dp(i) = max{dp(i-w[k]) + v[k], dp(i)}; 
print dp(Capacity);