배낭 - 프로그래밍 중 섹션을 이해할 수 없습니다.

Question

최근에 배낭 문제를 연구하고 구현하려고합니다. 따라서 배낭 값이 100이고 40, 60, 100 같은 특정 가중치와 같은 최적의 솔루션 아이디어를 이해하고 이해할 수 있습니다. 그런 다음 최적의 솔루션은 배낭 값을 채우거나 등가 적으로 100이됩니다. 나는 프로그래밍의 한 섹션에 머물렀고 튜토리얼을 사용하여 재귀를 시도했지만 이것이 실제로 어떻게 작동 하는지를 알 수 없었다. 제가 이해 한 것을 언급하자

/*A function or method to determine the max number*/ 
int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 

/*Knapsack function or method with parameters knapsack value - w, weights, amounts, number of elements*/ 
int Knapsack(int w, int weight[], int amt[], int n) 
{ 
    if(n == 0 || w == 0) 
    { 
     return 0; 
    } 

    if(weight[n - 1] > w) /*If the nth value is greater than the knapsack value, then there will no optimal solution*/ 
    { 
     return Knapsack(w, weight, amt, n - 1); 
    } 
    else 
    { 
     return max(amt[n - 1] + Knapsack(w - weight[n - 1], weight, amt, n - 1), Knapsack(w, weight, amt, n - 1)); /*Stuck in this section - It returns perfect solution but unable to understand how it's working. Debugged not getting the answer as expected*/ 
    } 
} 

int main(void) 
{ 
    int amt[3], weight[3], w, i, elements, n; 

    /*printf("Enter number of elements: "); 
    scanf("%d", &elements);*/ 

    printf("Enter the weight and amount individually up to 3: "); 

    for(i = 0; i < 3; i++) 
    { 
     scanf("%d %d", &weight[i], &amt[i]); 
    } 

    printf("\nEnter the knapsack value: "); 
    scanf("%d", &w); 

    n = sizeof(amt)/sizeof(amt[0]); 

    printf("%d %d", Knapsack(w, weight, amt, n), n); 

    return 0; 
} 

사람이 이해 할 수없는 오전 프로그래밍에 대한 간단한 작업 절차에서 설명 할 시간이 있다면 감사하겠습니다. 심지어 동적 프로그래밍을 사용하려고합니다. 하지만 그것은 조용한 복잡한 것 같습니다. 이 배낭 문제를 연구하는 완벽한 솔루션입니다 : napsack에 대한

Knapsack Problem

Answer 1

사용자가 모든 무게, 양, w 값을 입력하면 호출 순서에 대한 트리 구조를 그려야했습니다. , 따르는 내 예의 여기

는 (주에서 첫 번째 통화 Weight[1]=14 Amount[1]=15 Weight[2]=15 Amount[2]=10

W=20(knapsack capacity) Here value of n according to program would be 3.

Weight[0]=18 Amount[0]=17 , 값이 K 것, 변수 값이다 w [], a [], n) ====> K (20, w [], a [], 3) 다음 a[n-1]==>a[2]==>10 w[n-1]==>w[2]==>15 등 ... 값 변경

참고 : 매번 함수를 호출 한 후 값 변경 내용을 기억하십시오. IF 조건에서도 탭을 유지하십시오.

필기체를 무시하십시오. 감사. 우리는 재귀 문제를 처리하는 경우

, 우리는 우리가 (성 이름 아웃) STACK 때문에 LIFO 다루고있는 것을 기억해야합니다.

재귀 함수의 경우 Last라는 함수는 결과를 먼저 반환하고 First라는 함수는 결과를 마지막으로 반환합니다.문제는 나무 구조를 보면 이해할 수 있습니다. 감사.

Answer 2

이 프로그램은
주 :이 프로그램은 우리는 또한 일부 항목의 일부를 취할 수 있다고 가정합니다.

#include<stdio.h> 
void quick(float a[],float b[],float c[],int l,int u)  //quick(array ref, starting index, end index); 
{ 
    float p,temp;int i,j; 
    if(l<u) 
    { 
    p=a[l]; 
    i=l; 
    j=u; 
    while(i<j) 
    { 
     while(a[i] <= p && i<j)  //chane for desc 
    i++; 
     while(a[j]>p && i<=j)  //change for desc 
     j--; 
     if(i<=j) 
     { 
     temp=a[i]; 
     a[i]=a[j]; 
     a[j]=temp; 
     temp=b[i]; 
     b[i]=b[j]; 
     b[j]=temp; 
     temp=c[i]; 
     c[i]=c[j]; 
     c[j]=temp; 
     } 
    } 
    temp=a[j]; 
    a[j]=a[l]; 
    a[l]=temp; 
    temp=b[j]; 
    b[j]=b[l]; 
    b[l]=temp; 
    temp=c[j]; 
    c[j]=c[l]; 
    c[l]=temp; 

    quick(a,b,c,l,j-1); 
    quick(a,b,c,j+1,u); 
} 
} 

int main() 
{ 
    int t,i; 
    float p=0,w,cc; 
    printf("Enter number of elements :"); 
    scanf("%d",&t); 
    printf("Enter maximum allowed weight :"); 
    scanf("%d",&w); 
    float a[t],b[t],c[t]; 
    printf("Enter weights :"); 
    for(i=0;i<t;i++) 
    scanf("%f",&a[i]); 
    printf("Enter profits :"); 
    for(i=0;i<t;i++) 
    { 
     scanf("%f",&b[i]); 
     c[i]=b[i]/a[i]; 
    } 


    quick(c,a,b,0,t-1); 



    cc=0; 
    for(i=t-1;i>=0;i--) 
    { 
     if(cc>=w) 
     break; 

     if(cc+a[i]<=w) 
     { 
      p+=b[i]; 
      cc+=a[i]; 
     } 
     else 
     { 

      p+=b[i]*(w-cc)/a[i]; 
      cc+=a[i]; 
      break; 
     } 
    } 
    printf("Maximum profit %f",p); 

} 

무엇 내가 뭐하는 거지, 먼저 각 항목에 대한 이익/무게을 찾아서 배열에 저장합니다.
이 배열을 정렬하십시오.
최대이익/무게으로 항목을 선택하고 자루에 추가하십시오.
그런 다음 최대 값이 인 이익/중량이 인 다음 항목으로 이동하여 자루에 추가하십시오.
자루가 가득 찰 때까지 계속하십시오.