背包 - 编程时无法理解部分

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; 
} 

如果有人有时间简要的工作过程中，我无法理解编程来解释我将不胜感激。甚至尝试使用它的动态编程。但它似乎安静复杂。这是一个完美的解决方案，研究背包问题：

Knapsack Problem

Answer 1

我试图绘制一个树形结构，用于一旦用户输入了所有重量，金额，w值后会发生的调用顺序。

在我的例子

这里， 以下是变量的值，

Weight[0]=18 Amount[0]=17 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.

对于来自主第一个呼叫， 值将被K（ （20，w []，a []，3） 然后a[n-1]==>a[2]==>10 w[n-1]==>w[2]==>15等等...值变化

注意：请记住每次调用函数后的值更改。 也保留一个IF条件选项卡。

请忽略手写。谢谢。

当我们在处理递归问题，我们必须记住，我们正在处理堆栈，因此LIFO（后进先出）。

在递归函数的情况下，被调用Last的函数将首先返回结果，而称为First的函数将最终返回结果。如果你看到树形结构，你会明白它的问题。谢谢。

Answer 2

的程序napsack是
注：此程序假定我们还可以采取一些项目部分。

#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); 

} 

什么，我做的是，首先找到每个项目的利润/重量并保存一个阵列英寸
对这个数组进行排序。
然后选择最大的项目利润/重量，将其添加到袋中。
然后移动到最大利润/重量下一个项目，并将其添加到袋中。
继续这样做直到袋子满了。