求助代码分析

Question

小弟最近刚刚C++，对下面这个代码程序不很很懂，想请教一下这个算法的思路，最好能把这个算法在解决背包问题上的优缺点。希望大神帮帮忙，感激不尽。
回溯算法代码：
#include "iostream.h"
#include "conio.h"
#include "math.h"
#define N 7
struct object
{
float w;
float p;
float v;
}ob[N+1];
void sort(void);void main()
{
int i,k,w_cur,w_est,x[N+1],y[N+1],M;
    float p_cur,p_total,p_est;
    cout<<"请输入背包容量M：\n";
cin>>M;
    cout<<"请输入物品的重量和价值：\n";
for(i=0;i<N;i++)//输入物品的重量和价值并计算其价值重量比
{
cout<<"NO."<<i+1<<endl;
cin>>ob[i].w>>ob[i].p;
ob[i].v=ob[i].p/ob[i].w;
}
for(i=0;i<=N;i++)
{
x[i]=0;
y[i]=0;
}
    sort();//对物品按照价值重量比排序
    w_cur=0;  p_cur=0;  p_total=0;   k=0;
while(k>=0)
{
w_est=w_cur;
        p_est=p_cur;
for(i=k;i<N;i++)//使用贪心法求背包问题的解
{
w_est+=ob[i].w;
            if(w_est<M)  p_est+=ob[i].p;
            else
{
               p_est+=((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;
               break;
}
}
        if(p_est>p_total)//不需要回溯
{
for (i=k;i<N;i++)
{
if (w_cur+ob[i].w<=M)
{
w_cur = w_cur + ob[i].w;
                    p_cur = p_cur + ob[i].p;
                    y[i] = 1;
}
                else
{
                    y[i] = 0;   break;
}
}
        if (i>=N) 
{
if (p_cur>p_total) 
{
p_total = p_cur;   
k = N;
            for (i=0;i<N;i++)  x[i] = y[i];
                 }
             }
             else k = i + 1;
}
        else //回溯
{
while ((i>=0)&&(y[i]==0))  
i=i-1;
            if (i<0)  break;
            else 
{
w_cur = w_cur - ob[i].w;
        p_cur = p_cur - ob[i].p;
                y[i] = 0;   
k = i + 1;
}
}
}
    k=1;
    for(i=0;i<N;i++)//输出
        if(x[i]!=0)
{ 
cout<<"No "<<k<<"物品重量为："<<ob[i].w<<"价值为："<<ob[i].p<<endl;
        k++;
}
cout<<p_total;
    getch();
}
void sort(void)
{
int i,j;
struct object temp;
    for(i=0;i<N;i++)
    for(j=i+1;j<N;j++)
if(ob[j].v>ob[i].v)
{
temp=ob[i];
ob[i]=ob[j];
ob[j]=temp;
}
}

Answer 1

我主要是对这个地方p_est+=((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;不太懂
还有后面的if(p_est>p_total)//不需要回溯
{
for (i=k;i<N;i++)
{
if (w_cur+ob[i].w<=M)
{
w_cur = w_cur + ob[i].w;
  p_cur = p_cur + ob[i].p;
  y[i] = 1;
}
  else
{
  y[i] = 0; break;
}
}
if (i>=N)  
{
if (p_cur>p_total)  
{
p_total = p_cur;   
k = N;
for (i=0;i<N;i++) x[i] = y[i];
  }
  }
  else k = i + 1;
}
  else //回溯
这是构造回溯的解空间还是直接找最优解了？