新微赢技术网

标题: 回溯法解决转载问题 [打印本页]

作者: 火箭筒︻$▅ 时间: 2009-11-3 03:20
标题: 回溯法解决转载问题
#include <iostream.h>
const int MAX=10;
const int n=3;
const int i=1;
int w[]={10,40,40};
int cw=0,bestw=0,r=90,c=50;
int bestx[MAX],x[MAX];
int Backtrack(int i)
{
if(i>n)
{
      if(cw>bestw)//比上次大更新记录
      {
         for(int j=1;j<=n;j++)
            bestx[j]=x[j];
         bestw=cw;
      }
      return 0;
}
r-=w[i];
if(cw+w[i]<=c)//能装下搜索左子树
{
      x[i]=1;
      cw+=w[i];
      Backtrack(i+1);
      cw-=w[i];
}
if(cw+r>bestw)//搜索右子树加上剩下的比现在最优的大，可能是最优解
{
      x[i]=0;
      Backtrack(i+1);
}
r+=w[i];
}
int main()
{
Backtrack(i);
cout<<bestw<<endl;
for(int i=0;i<MAX;i++)
      cout<<bestx[i];
cout<<endl;
return 0;
}

编译是有个警告：就是说不是每个执行路径都有返回值，但是加在BackT函数最后后，结果还是一样，应该是50才对啊，怎么是40呢

作者: Оo水流影在. 时间: 2009-11-3 03:20
程序代码：
#include <iostream>
using namespace std;

const int MAX=10;
const int n=3;
//const int i=1;
int w[]={10,40,40};
int cw=0,bestw=0,r=90,c=50;
int bestx[MAX],x[MAX];
int Backtrack(int i)
{
      if(i>=n)
      {
            if(cw>bestw)
            {
                     for(int j=0;j<n;j++)
                              bestx[j]=x[j];
                     bestw=cw;
            }
            return 0;
      }
      r-=w[i];
      if(cw+w[i]<=c)
      {
            x[i]=1;
            cw+=w[i];
            Backtrack(i+1);
            cw-=w[i];
      }
      if(cw+r>bestw)
      {
            x[i]=0;
            Backtrack(i+1);
      }
      r+=w[i];
}
int main()
{
      Backtrack(0);
      cout<<bestw<<endl;
      for(int i=0;i<n;i++)
            cout<<bestx[i];
      cout<<endl;
      scanf("%*s");
      return 0;
}

作者: ゛， 时间: 2009-11-3 03:20
就是把i赋值为0吗

欢迎光临新微赢技术网 (http://bbs.weiying.cn/)