배낭 값의 프린트

Question

배낭 문제에 대한 해결책은 다음과 같습니다. (wt []는 가중치 배열, val []은 값 배열, n은 배열 크기, index는 현재 항목입니다. (재귀 위해) 노력하고 편곡 날씨 여부 항목이 내가 용액에 포함 된 나타내는 배열입니다.

int knapSack(int W, int wt[], int val[], int n, int index, int arr[]) 
{ 
    if (n == index || W == 0) 
     return 0; 
    if (wt[index] > W) 
     return knapSack(W, wt, val, n, index+1); 

    int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1); 
    int without=knapSack(W, wt, val, n, index+1); 

    if(with>without){ 
     arr[index]=1; 
     return with; 
    } 
    else{ 
     arr[index]=0; 
     return without; 
    } 

} 

내가 인쇄하려고,이 재귀 용액에 설정하여, 선택되는 항목 배열 (res)에서 가져온 인덱스를 1로 설정합니다. 내가 이해하는 것처럼 with>without이면 현재 항목 또는 #index를 선택하고 있음을 의미하므로 올바른 값을 반환하지 않는 이유는 무엇입니까?
이유에 대해 재귀 알고리즘을 사용하고 있습니다. 메모 작성 버전을 사용하는 것이 더 쉽습니다. 예 :
가중치 : 5 개 6 7 10 11
값 : 2 3 4 5 6 9
W = 25
어레이 입술 5 개 것들을 반환한다. 솔루션이 항목 2,3,5 (색인 1부터 시작)와 함께 18 일 때.

Answer 1

전제 한가 : 코드에서, 재귀가 knapSack은 컴파일 오류가 발생한다 arr를 통과하지 않는 호출, 난 그냥 복사/붙여 넣기 오류입니다 가정합니다. 여전히 올바르지 당신이 표시된 결과 arr 값이 모든 1 당신이 제안 된 데이터와 함께,하지만 01011 :

전제 2.

는 with가 without보다 크면, 함수 실행시에 가상의 상황을 고려 다음 with 계산시 arr 올바른 값으로 채워진다; 그러나 arr 값을 덮어 쓰려는 without 계산을 시작하십시오.

with이 without보다 커서 반환 된 arr은 잘못된 것이므로 문제의 원인입니다.

간단한 수정 예를 들어,이 without 계산에 의해 덮어 쓰기하지 않을 수 있도록 with 계산에 의해 반환 된 arr의 사본을하는 것입니다 :

int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1, arr); 

// copy the "with" arr 
int arrWith[n]; 
copyArr(arr, arrWith, n); 

int without=knapSack(W, wt, val, n, index+1, arr); 

if(with>without){ 
    // restore the "with" arr 
    copyArr(arrWith, arr, n); 

    arr[index]=1; 
    return with; 
} 
else{ 
    arr[index]=0; 
    return without; 
} 

copyArr는 단순히 :

void copyArr(int arr[], int arrDest[], int n) { 
    int i; 
    for(i = 0; i < n; i++) { 
     arrDest[i] = arr[i]; 
    } 
} 

arr의 결과 값은 01101입니다.