查看: 1664|回复: 2

回溯法解决转载问题

[复制链接]

火箭筒︻$▅

电梯直达

1^#

发表于 2009-11-3 03:20:07 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

#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呢

收藏0

使用道具举报

Оo水流影在.

2^#

发表于 2009-11-3 03:20:08 | 只看该作者

程序代码：
#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;
}

回复支持反对

使用道具举报

゛，

3^#

发表于 2009-11-3 03:20:09 | 只看该作者

就是把i赋值为0吗

回复支持反对

使用道具举报

返回列表

		自动登录	找回密码
密码			注册