分支限界法带时限进程排序的问题

Question

题目描述
用分支限界法解决问题，带时限的排序问题可描述为：设有n个进程和一台处理机，每个进程所需的处理时间、要求的时限和收益可用三元组（pi, di, ti），0<=i<n表示，其中，进程i的所需时间为ti，如果进程i能够在时限di内完成，将可收益pi，求使得总收益最大的进程子集J。
输入
第一行输入n（0<n<15）的值；第二行输入pi；第三行输入di；第四行输入ti （i=0，…，n-1且进程已经按时限非减次序排列）。
输出
xi（用固定长度n-元组xi表示，xi=0或1，i=0，…，n-1），每个xi后带有一个空格。
样例输入
4
5 3 6 10
1 1 2 3
1 1 1 2
样例输出
0 0 1 1
下面的代码该怎么改

#include <iostream>  
#include <vector>  
#include <queue>  
#include <algorithm>  
  
using namespace std;  
const int N = 15;
int p[N],d[N],t[N];
int n;
int U=0;
int ans[N];

struct Node {
    int time; // 当前时间  
    int zy;
    int current;
    int c;//已损失的进程价值 
    int u;// 已损失的进程价值 +后面全部进程价值之和 
    struct Node *parent;
};  

void print_ans(Node *x){
    if(x->current>=0)print_ans(x->parent);
    cout<<x->zy<<" ";
}

bool feassible(Node *x){
//    cout<<"time="<<x->time<<" di="<<d[x->current]<<endl;
//    cout<<"c="<<x->c<<" U="<<U<<endl;
    if(x->time>d[x->current]||x->c>=U){
        return false;
    }
    if(x->u<U){
        U=x->u;
    }
    return true;
}

void fifobb(Node* tt){
    queue <struct Node *> lst;
    Node *E =tt;
    int m=-1;
    m++;
    while(m<=n-1){
//        cout<<m<<" ";
        for(int i=0;i<2;i++){
            Node *x = new Node;
            x->zy=(i==0);
            x->parent=E;
            x->current=m;
            if(x->zy==0){//不要
                x->time=E->time;
                x->c=E->c+p[m];
                x->u=E->u;
            }else{//要 
                x->time=E->time+t[m];
                x->c=E->c;
                x->u=E->u-p[m];
            }

            if(feassible(x)){
                if(m==n-1){
                    print_ans(x);
                }
                lst.push(x);
            }
        }
        E=lst.front();
        lst.pop();
        m=m+1;
    }
}
  
int main() {  
    cin >> n;  

    for (int i = 0; i < n; ++i) {  
        cin >> p[i];  
        U+=p[i];
    }  
    for (int i = 0; i < n; ++i) {  
        cin >> d[i];  
    }  
    for (int i = 0; i < n; ++i) {  
        cin >> t[i];  
    }  
      Node *t = new Node;

    t->c=0;
    t->time=0;
    t->zy=-1; 
    t->parent=NULL;
    t->current=-1;
    t->u=U;
    fifobb(t);
    return 0;  
}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

针对你提出的问题，我将给出一些修改建议和代码示例，帮助你理解如何实现分支限界法解决带时限的进程排序问题。

1. 初始化U

在main函数中，初始化U为所有进程收益的总和。注意，这里不需要在for循环中累加U，因为U是一个全局变量，只需要初始化一次即可。

int main() {
    cin >> n;
    U = 0; // 初始化U为0
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        U += p[i]; // 累加所有进程的收益
    }
    // ... 其他代码
}

2. 修改feassible函数

feassible函数需要判断当前节点是否满足时限要求。如果当前时间加上当前进程的处理时间超过了时限，或者已损失的进程价值加上剩余进程的收益之和小于等于U，则当前节点不可行。

bool feassible(Node *x) {
    if (x->time + t[x->current] > d[x->current]) { // 判断是否满足时限
        return false;
    }
    // 更新最大收益U
    if (x->c + x->u < U) {
        U = x->c + x->u;
    }
    return true;
}

3. 修改fifobb函数

在fifobb函数中，需要正确处理进程的选择，并更新time和c。同时，需要记录选择的进程，以便最后输出。

void fifobb(Node* tt) {
    // ... 其他代码
    for (int i = 0; i < 2; i++) {
        Node *x = new Node;
        x->zy = (i == 1); // 选择当前进程
        x->parent = E;
        x->current = m;
        if (x->zy) { // 选择当前进程
            x->time = E->time + t[m];
            x->c = E->c; // 当前已损失的进程价值不变
            x->u = E->u - p[m]; // 更新剩余进程的收益
            ans[m] = 1; // 记录选择的进程
        } else {
            x->time = E->time;
            x->c = E->c + p[m]; // 当前已损失的进程价值加上当前进程的收益
            x->u = E->u; // 剩余进程的收益不变
            ans[m] = 0; // 记录未选择的进程
        }
        // ... 其他代码
    }
}

4. 输出最终结果

在fifobb函数的最后，当找到一个可行解时，输出选择的进程集合。

if (feassible(x) && m == n - 1) {
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

5. 其他注意事项

• 确保ans数组在main函数中初始化为0。
• 考虑使用优先队列（最小堆）来优化搜索过程，优先扩展收益最大的节点。

参考资料

• 分支限界法
• C++ STL queue和priority_queue

请注意，上述代码仅为示例，可能需要根据实际情况进行调整。希望这些建议能帮助你解决问题。