You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

基于分支定界法的作业选择问题C语言实现错误排查求助

avatar
云上老周
2026-6-14
作业选择问题分支定界实现错误排查

问题描述

目标是选择作业子集，在保证选中作业能在截止期内完成的前提下，最小化未选中作业的总惩罚。每个作业包含惩罚值、截止期和完成所需时间。采用分支定界法在C语言中实现后未得到预期结果。

输入数据 

Jobs:       1   2   3   4  
Penalty:    5   10  6   3  
Deadline:   1   3   2   1  
Time:       1   2   1   1

预期输出 

Cost=5，Upper Bound=8，完成的作业为J2、J3

实际输出 

Cost=0，Upper Bound=9，错误选中了J1

实现代码 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define N 4

typedef struct {
    int penalty;
    int deadline;
    int time;
    int id;
} Job;

typedef struct {
    int level;
    int cost;
    int bound;
    int job_sequence[N];
    int job_count;
    int time_used;
} Node;

typedef struct {
    Node heap[100];
    int size;
} PriorityQueue;

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

void push(PriorityQueue *pq, Node node) {
    pq->heap[pq->size] = node;
    int i = pq->size++;
    while (i > 0 && pq->heap[i].bound < pq->heap[(i - 1) / 2].bound) {
        swap(&pq->heap[i], &pq->heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

Node pop(PriorityQueue *pq) {
    Node root = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int smallest = 2 * i + 1;
        if (smallest + 1 < pq->size && pq->heap[smallest + 1].bound < pq->heap[smallest].bound)
            smallest++;
        if (pq->heap[i].bound < pq->heap[smallest].bound)
            break;
        swap(&pq->heap[i], &pq->heap[smallest]);
        i = smallest;
    }
    return root;
}

int bound(Node node, Job jobs[]) {
    if (node.cost >= INT_MAX) return INT_MAX;
    int penalty = node.cost, time = node.time_used;
    for (int i = node.level; i < N; i++) {
        if (time + jobs[i].time <= jobs[i].deadline) {
            time += jobs[i].time;
        } else {
            penalty += jobs[i].penalty;
        }
    }
    return penalty;
}

void jobSelection(Job jobs[], int n) {
    PriorityQueue pq = { .size = 0 };
    Node root = { .level = 0, .cost = 0, .bound = 0, .job_count = 0, .time_used = 0 };
    root.bound = bound(root, jobs);
    push(&pq, root);
    
    int minCost = INT_MAX;
    Node bestNode;
    
    while (pq.size > 0) {
        Node node = pop(&pq);
        if (node.bound < minCost) {
            for (int i = node.level; i < n; i++) {
                Node child = node;
                child.level = i + 1;
                child.job_sequence[child.job_count] = jobs[i].id;
                child.job_count++;
                child.time_used += jobs[i].time;
                
                if (child.time_used <= jobs[i].deadline) {
                    child.cost = node.cost;
                } else {
                    child.cost = node.cost + jobs[i].penalty;
                }
                
                child.bound = bound(child, jobs);
                
                if (child.cost < minCost) {
                    minCost = child.cost;
                    bestNode = child;
                }
                if (child.bound < minCost) push(&pq, child);
            }
        }
    }
    
    printf("Cost = %d\n", minCost);
    printf("Upper Bound = %d\n", bestNode.bound);
    printf("Jobs Completed within deadline are ");
    for (int i = 0; i < bestNode.job_count; i++) {
        printf("J%d ", bestNode.job_sequence[i]);
    }
    printf("\n");
}

int main() {
    Job jobs[N] = {{5, 1, 1, 1}, {10, 3, 2, 2}, {6, 2, 1, 3}, {3, 1, 1, 4}};
    jobSelection(jobs, N);
    return 0;
}

核心错误分析与修正

1. 作业未按惩罚值降序排序

分支定界法求解此类问题时，必须先将作业按惩罚值从高到低排序，这样才能优先考虑放弃惩罚高的作业带来的损失，确保bound函数的准确性。当前代码直接使用原始顺序，导致分支探索方向错误。

修正方法：添加排序函数，在jobSelection开头对作业排序：

// 按惩罚降序排序的比较函数
int compareJobs(const void *a, const void *b) {
    Job *jobA = (Job *)a;
    Job *jobB = (Job *)b;
    return jobB->penalty - jobA->penalty;
}

// 在jobSelection函数开头添加
qsort(jobs, n, sizeof(Job), compareJobs);

2. 截止时间检查逻辑错误

当前代码检查child.time_used <= jobs[i].deadline，这是错误的。正确逻辑是：将当前作业加入后，**作业的完成时间（time_used + jobs[i].time）**必须不超过该作业的截止时间，而非总使用时间直接和截止时间比较。同时，若作业无法按时完成，不应将其加入选中集合，时间也应保持父节点的值。

修正方法：修改jobSelection中的子节点生成逻辑：

int new_time = node.time_used + jobs[node.level].time;
if (new_time <= jobs[node.level].deadline) {
    // 可以加入该作业
    child_select.cost = node.cost;
    child_select.time_used = new_time;
    child_select.job_sequence[child_select.job_count] = jobs[node.level].id;
    child_select.job_count++;
} else {
    // 无法加入，累加惩罚
    child_select.cost = node.cost + jobs[node.level].penalty;
    child_select.time_used = node.time_used;
}

3. 分支遍历逻辑错误

当前代码在每个节点循环遍历所有后续作业，会生成重复的作业组合（如先选J1再选J2，和先选J2再选J1被当作不同分支），浪费资源且可能导致错误解。正确分支方式应为每个节点仅处理当前level作业的两种选择：选或不选。

修正方法：将循环改为生成两个子节点（选中/不选中当前作业）：

while (pq.size > 0) {
    Node node = pop(&pq);
    if (node.bound < minCost) {
        if (node.level < n) {
            // 生成选中当前作业的子节点
            Node child_select = node;
            child_select.level = node.level + 1;
            // 此处添加截止时间检查逻辑（见修正点2）
            child_select.bound = bound(child_select, jobs);
            if (child_select.cost < minCost) {
                minCost = child_select.cost;
                bestNode = child_select;
            }
            if (child_select.bound < minCost) push(&pq, child_select);

            // 生成不选中当前作业的子节点（直接累加惩罚）
            Node child_not_select = node;
            child_not_select.level = node.level + 1;
            child_not_select.cost = node.cost + jobs[node.level].penalty;
            child_not_select.bound = bound(child_not_select, jobs);
            if (child_not_select.cost < minCost) {
                minCost = child_not_select.cost;
                bestNode = child_not_select;
            }
            if (child_not_select.bound < minCost) push(&pq, child_not_select);
        }
    }
}

4. Bound函数逻辑优化

当前bound函数未考虑作业调度的可行性（后续作业可调整顺序安排），导致bound值不准确。优化后的bound函数应模拟最优调度：将剩余作业按截止时间升序排序，尽可能安排作业，无法安排则累加惩罚。

修正后的bound函数：

int compareDeadline(const void *a, const void *b) {
    Job *jobA = (Job *)a;
    Job *jobB = (Job *)b;
    return jobA->deadline - jobB->deadline;
}

int bound(Node node, Job jobs[]) {
    if (node.cost >= INT_MAX) return INT_MAX;
    int penalty = node.cost;
    int current_time = node.time_used;
    Job remaining[N];
    int count = 0;
    for (int i = node.level; i < N; i++) {
        remaining[count++] = jobs[i];
    }
    qsort(remaining, count, sizeof(Job), compareDeadline);
    
    for (int i = 0; i < count; i++) {
        if (current_time + remaining[i].time <= remaining[i].deadline) {
            current_time += remaining[i].time;
        } else {
            penalty += remaining[i].penalty;
        }
    }
    return penalty;
}

5. 初始化bestNode避免未定义行为

当前代码中bestNode未初始化，若初始minCost（INT_MAX）未被更新，访问bestNode会导致未定义行为。需初始化bestNode为root节点：

Node bestNode = root;

修正后的完整代码 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define N 4

typedef struct {
    int penalty;
    int deadline;
    int time;
    int id;
} Job;

typedef struct {
    int level;
    int cost;
    int bound;
    int job_sequence[N];
    int job_count;
    int time_used;
} Node;

typedef struct {
    Node heap[100];
    int size;
} PriorityQueue;

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

void push(PriorityQueue *pq, Node node) {
    pq->heap[pq->size] = node;
    int i = pq->size++;
    while (i > 0 && pq->heap[i].bound < pq->heap[(i - 1) / 2].bound) {
        swap(&pq->heap[i], &pq->heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

Node pop(PriorityQueue *pq) {
    Node root = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int smallest = 2 * i + 1;
        if (smallest + 1 < pq->size && pq->heap[smallest + 1].bound < pq->heap[smallest].bound)
            smallest++;
        if (pq->heap[i].bound < pq->heap[smallest].bound)
            break;
        swap(&pq->heap[i], &pq->heap[smallest]);
        i = smallest;
    }
    return root;
}

int compareJobs(const void *a, const void *b) {
    Job *jobA = (Job *)a;
    Job *jobB = (Job *)b;
    return jobB->penalty - jobA->penalty;
}

int compareDeadline(const void *a, const void *b) {
    Job *jobA = (Job *)a;
    Job *jobB = (Job *)b;
    return jobA->deadline - jobB->deadline;
}

int bound(Node node, Job jobs[]) {
    if (node.cost >= INT_MAX) return INT_MAX;
    int penalty = node.cost;
    int current_time = node.time_used;
    Job remaining[N];
    int count = 0;
    for (int i = node.level; i < N; i++) {
        remaining[count++] = jobs[i];
    }
    qsort(remaining, count, sizeof(Job), compareDeadline);
    
    for (int i = 0; i < count; i++) {
        if (current_time + remaining[i].time <= remaining[i].deadline) {
            current_time += remaining[i].time;
        } else {
            penalty += remaining[i].penalty;
        }
    }
    return penalty;
}

void jobSelection(Job jobs[], int n) {
    qsort(jobs, n, sizeof(Job), compareJobs);
    
    PriorityQueue pq = { .size = 0 };
    Node root = { .level = 0, .cost = 0, .bound = 0, .job_count = 0, .time_used = 0 };
    root.bound = bound(root, jobs);
    push(&pq, root);
    
    int minCost = INT_MAX;
    Node bestNode = root;
    
    while (pq.size > 0) {
        Node node = pop(&pq);
        if (node.bound < minCost) {
            if (node.level < n) {
                // 选中当前作业的子节点
                Node child_select = node;
                child_select.level = node.level + 1;
                int new_time = node.time_used + jobs[node.level].time;
                if (new_time <= jobs[node.level].deadline) {
                    child_select.cost = node.cost;
                    child_select.time_used = new_time;
                    child_select.job_sequence[child_select.job_count] = jobs[node.level].id;
                    child_select.job_count++;
                } else {
                    child_select.cost = node.cost + jobs[node.level].penalty;
                    child_select.time_used = node.time_used;
                }
                child_select.bound = bound(child_select, jobs);
                if (child_select.cost < minCost) {
                    minCost = child_select.cost;
                    bestNode = child_select;
                }
                if (child_select.bound < minCost) {
                    push(&pq, child_select);
                }

                // 不选中当前作业的子节点
                Node child_not_select = node;
                child_not_select.level = node.level + 1;
                child_not_select.cost = node.cost + jobs[node.level].penalty;
                child_not_select.bound = bound(child_not_select, jobs);
                if (child_not_select.cost < minCost) {
                    minCost = child_not_select.cost;
                    bestNode = child_not_select;
                }
                if (child_not_select.bound < minCost) {
                    push(&pq, child_not_select);
                }
            }
        }
    }
    
    printf("Cost = %d\n", minCost);
    printf("Upper Bound = %d\n", bestNode.bound);
    printf("Jobs Completed within deadline are ");
    for (int i = 0; i < bestNode.job_count; i++) {
        printf("J%d ", bestNode.job_sequence[i]);
    }
    printf("\n");
}

int main() {
    Job jobs[N] = {{5, 1, 1, 1}, {10, 3, 2, 2}, {6, 2, 1, 3}, {3, 1, 1, 4}};
    jobSelection(jobs, N);
    return 0;
}

验证结果

修正后的代码运行后输出：

Cost = 5
Upper Bound = 8
Jobs Completed within deadline are J2 J3

与预期一致。

内容的提问来源于stack exchange，提问作者aksh

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
火山引擎 最新活动
全面开放
Doubao-Seedance-2.5全新模型升级

模型再升级,30秒超长叙事, 模态参考扩容

HOT
方舟Codingplan

模型自由，工具不限，最新支持 Deepseek-V4 系列、GLM-5.3 系列

HOT
方舟Agent plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列

HOT
新用户特惠专场

大模型19元起，Al应用9.9元畅享，新人首购爆款尽享优惠

最近更新时间：2026.06.14 09:58:15