请问为什么结果全为0，逻辑有问题吗？怎么改？

Question

#include<stdio.h>
#include
#include<string.h>
#define MAX 20
using namespace std;
struct NodeType //队列结点类型
{int no; //结点编号
int x[MAX];
int y[MAX];
int i; //步骤编号
int f1; //已经分配M1的执行时间
int f2; //已经分配M2的执行时间
int lb; //下界
bool operator<(const NodeType &s) const //重载<关系函数
{return lb>s.lb; //1b越小越优先出队
}
};
void bound(NodeType &e) //求结点e的限界值
{ int n,b[20];int sum=0;
for (int i=1;i<=n;i++) //扫描所有
if (e.y[i]==0) sum+=b[i];
//仅累计e.x中还没有分配的的b时间
e.lb=e.f1+sum;}
//问题表示
int INF;
int n=4;
int a[MAX]={0,5,12,4,8}; //M1上的执行时间,不用下标0的元素
int b[MAX]={0,6,2,14,7};
//求解结果表示
int bestf=INF; //存放最优调度时间
int bestx[MAX] ; //存放当前最佳调度
int total=1; //结点个数累计
int bfs() //求解流水调度问题
{ NodeType e,e1;
priority_queue qu; //定义优先队列
memset(e.x,0,sizeof(e.x)); //初始化根结点的x
memset(e.y,0,sizeof(e.y)); //初始化根结点的y
e.i=0; //根结点
e.f1=0;
e.f2=0;
bound(e);
e.no=total++;
qu.push(e); //根结点进队列
while (!qu.empty())
{ e=qu.top();qu.pop();//出队结点e
if (e.i==n) //达到叶子结点
{if (e.f2<bestf) //比较求最优解
{ bestf=e.f2;
for (int j1=1;j1<=n;j1++)
bestx[j1]=e.x[j1];
}
}
e1.i=e.i+1; //扩展分配下一个步骤的，对应结点e1
for (int j=1;j<=n;j++) //考虑所有的n个
{int i1;
if (e.y[j]==1) continue; //i是否已分配，若已分配，跳过
for (int i1=1;i1<=n;i1++) //复制e.x得到e1.x
e1.x[i1]=e.x[i1];
for(int i2=1;i2<=n;i2++) //复制e.y得到e1.y
e1.y[i2]=e.y[i2];
e1.x[e1.i]=j; //为第1步分配j
e1.y[j]=1; //表示j已经分配
e1.f1=e.f1+a[j]; //求f1=f1+a[j]
e1.f2=max(e.f2,e1.f1)+b[j];//求f[i+1]=max(f2[i],f1)+b[j]
bound(e1);
if (e1.f2<=bestf)
{ e1.no=total++; //结点编号增加1
qu.push(e1);
}
}
}
}
int main()
{ bfs();
printf("最优方案:\n");
for (int k=1;k<=n;k++)
printf(" 第%d步执行%d\n",k,bestx[k]);
printf(" 总时间=%d\n",bestf);
}

Answer 1

#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX 5 //20
using namespace std;
struct NodeType //队列结点类型
{
    int no; //结点编号
    int x[MAX];
    int y[MAX];
    int i; //步骤编号
    int f1; //已经分配M1的执行时间
    int f2; //已经分配M2的执行时间
    int lb; //下界
    bool operator<(const NodeType &s) const //重载<关系函数
    {
        return lb>s.lb; //1b越小越优先出队
    }
};
void bound(NodeType &e) //求结点e的限界值
{
    int n=4,b[20];int sum=0;
    for (int i=1;i<=n;i++) //扫描所有
        if (e.y[i]==0) sum+=b[i];
    //仅累计e.x中还没有分配的的b时间
    e.lb=e.f1+sum;
}
//问题表示
int INF=10000;
int n=4;
int a[MAX]={0,5,12,4,8}; //M1上的执行时间,不用下标0的元素
int b[MAX]={0,6,2,14,7};
//求解结果表示
int bestf=INF; //存放最优调度时间
int bestx[MAX] ; //存放当前最佳调度
int total=1; //结点个数累计
void bfs() //求解流水调度问题
{
    NodeType e,e1;
    priority_queue<NodeType> qu; //定义优先队列
    for (int i=0;i<MAX;i++) {
        e.x[i]=0;
        e.y[i]=0;
    }
    e.i=0; //根结点
    e.f1=0;
    e.f2=0;
    bound(e);
    e.no=total++;
    qu.push(e); //根结点进队列
    while (!qu.empty())
    {
        e=qu.top();qu.pop();//出队结点e
        if (e.i==n) //达到叶子结点
        {
            if (e.f2<bestf) //比较求最优解
            {
                bestf=e.f2;
                for (int j1=1;j1<=n;j1++)
                    bestx[j1]=e.x[j1];
            }
        }
        e1.i=e.i+1; //扩展分配下一个步骤的，对应结点e1
        for (int j=1;j<=n;j++) //考虑所有的n个
        {
            //int i1;
            if (e.y[j]==1) continue; //i是否已分配，若已分配，跳过
            for (int i1=1;i1<=n;i1++) //复制e.x得到e1.x
                e1.x[i1]=e.x[i1];
            for(int i2=1;i2<=n;i2++) //复制e.y得到e1.y
                e1.y[i2]=e.y[i2];
            e1.x[e1.i]=j; //为第1步分配j
            e1.y[j]=1; //表示j已经分配
            e1.f1=e.f1+a[j]; //求f1=f1+a[j]
            e1.f2=max(e.f2,e1.f1)+b[j];//求f[i+1]=max(f2[i],f1)+b[j]
            bound(e1);
            if (e1.f2<=bestf) {
                e1.no=total++; //结点编号增加1
                qu.push(e1);
            }
        }
    }
}
int main() {
    bfs();
    printf("最优方案:\n");
    for (int k=1;k<=n;k++)
        printf(" 第%d步执行%d\n",k,bestx[k]);
    printf(" 总时间=%d\n",bestf);
}
//最优方案:
// 第1步执行3
// 第2步执行1
// 第3步执行4
// 第4步执行2
// 总时间=33
//