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

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

napsack 的程序是
note:This 程序假定我们也可以取一些项目的分数。

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

}

我在做的是，首先找到每个项目的profit/weight并将其保存在一个数组中。
对这个数组进行排序。
然后select最大值profit/weight的物品，加入袋子
然后移动到下一个最大 profit/weight 的项目并将其添加到麻袋中。
继续这样做直到麻袋满为止。

Answer 2

我已尝试为用户输入所有重量、数量、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.

对于来自 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（后进先出）。

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

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

Knapsack - Unable To Understand a Section While Programming

c

knapsack-problem