c - Knapsack - 编程时无法理解某个部分

Question

最近，我正在尝试研究和实现背包问题(我几年前研究过)。所以我可以理解并有最优解的想法，比如如果背包值(value)是 100，并且有特定的权重，比如 40、60、100。那么最优解将是 100 来填充或相当于背包值(value)。我停留在编程的一个部分，尽管尝试使用教程进行递归，但无法弄清楚这实际上是如何工作的。让我评论一下我已经理解:

/*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 值后发生的调用顺序绘制一个树结构。

在我的示例中， 以下是变量的值，

重量[0]=18 数量[0]=17 重量[1]=14 数量[1]=15 重量[2]=15 数量[2]=10

W=20(背包容量) 根据程序 n 的值为 3。

对于来自 main 的第一次调用， 值将为 K(w, W[], a[], n)====> K(20,w[], a[], 3) 然后 a[n-1]==>a[2]==>10 w[n-1]==>w[2]==>15 等等...值改变

注意:请记住每次调用函数后值的变化。 还要密切关注 IF 条件。

请忽略手写。谢谢。

当我们处理递归问题时，我们需要记住我们正在处理 STACK，因此是 LIFO(后进先出)。

在递归函数的情况下，最后调用的函数将首先返回结果，而调用 First 的函数将最后返回结果。如果您看到树结构，您就会明白您的问题。谢谢。