工厂流水线工作安排，某工厂生产的产品需要经历3道工序，为了提高效率,三道工序利用流水作业的方式进行，根据产品规模不同，每个产品的每道工序耗费的时长不同。今天，工厂接收到一批订单需要生产n件产品，第i个产品的第j道工序的时长为Tijo
（1）请你为工厂制定一个加工顺序，使得生产n件产品的总时长最少。
(2）要求输入n不小于10，并请分别将n递增，至少给出3组运行数据，
比较程序的运行时间。
我的代码为什么只能运行十以内的任务数超过十就运行结果错误了麻烦指正修改，
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
#define max_m 3 // 机器数
#define max_t 200 // 任务数上限
#define INF 1000
int n; // 实际任务数
int t_m[max_t][max_m]; // 存储机器与任务的矩阵
typedef struct Node {
int sum1;
int sum2;
int lb;
int t_num; // 已执行任务数
int t; // 当前任务
bool visited[max_t]; // 标记已执行任务
int es[max_t]; // 执行序列
bool operator< (const Node &p) const {
return p.lb < lb;
}
} Node;
priority_queue<Node> pp;
int up;
void get_up() { // 获取上界，任务从1到4按序执行
up = 0;
for(int i = 0; i < max_t; i++)
up += t_m[i][max_m-1];
for(int j = 0; j < max_m-1; j++)
up += t_m[0][j];
}
int get_lb(Node node) { // 获取目标函数值
node.lb = node.sum2;
int min = INF;
for(int i = 0; i < n; i++)
if(!node.visited[i]) {
if(i != node.t) {
if (i != node.t) {
node.lb += t_m[i][1]; // 加上剩余任务在第二个机器上完成时间和
} // 加上剩余任务在第二个机器上完成时间和
if(t_m[i][2] < min)
min = t_m[i][2];
}
}
node.lb += min; // 加上剩余任务中执行时间最短的一个
return node.lb;
}
void solve() {
get_up();
int sequence[max_t];
Node first; // 初始化第一个节点
first.t_num = 0;
first.lb = 0;
first.t = -1;
first.sum1 = 0;
first.sum2 = 0;
for(int i = 0; i < n; i++)
first.visited[i] = false;
for(int j = 0; j < n; j++)
first.es[j] = -1;
pp.push(first);
while(pp.size()) {
Node tmp= pp.top();
pp.pop();
if(tmp.t_num == n-1) {
int ans;
for(int i = 0; i < n; i++) {
sequence[i] = tmp.es[i];
if(!tmp.visited[i]) // 找到最后一个未执行任务
ans = i;
}
sequence[n-1] = ans;
break;
} else {
Node next;
for(int i = 0; i < n; i++)
next.visited[i] = false;
for(int i = 0; i < n; i++) {
if(!tmp.visited[i]) {
next.t_num = tmp.t_num + 1;
next.t = i;
for(int j = 0; j < n; j++) // 继承执行序列
next.es[j] = tmp.es[j];
next.es[next.t_num-1] = i;
next.sum1 = tmp.sum1 + t_m[i][0];
if(next.sum1 > tmp.sum2)
next.sum2 = next.sum1 + t_m[i][1];
else
next.sum2 = tmp.sum2 + t_m[i][1];
for(int j = 0; j < n; j++)
next.visited[j] = tmp.visited[j]; // 继承任务操作标记
next.visited[i] = true;
next.lb = get_lb(next);
if(next.lb <= up) {
pp.push(next);
}
}
}
}
}
printf("最优解任务执行序列为：");
for(int i = 0; i < n; i++) {
printf("%d ", sequence[i] + 1);
}
}
int main() {
printf("请输入任务数：");
scanf("%d", &n);
printf("请输入任务-机器矩阵：\n");
for(int i = 0; i < n; i++)
for(int j = 0; j < max_m; j++) {
scanf("%d", &t_m[i][j]);
if(j == max_m - 1)
getchar();
}
solve();
}
你第七行不是定义了任务数上线吗 最大11
代码块：
方法1：
#include <stdio.h>
struct student
{
int num;
char name[10];
float score[3];
float aver;
} stu[10];
void input(struct student s[], int n);
void average(struct student s[], int n);
void high_score(struct student s[], int n);
int main()
{
input(stu, 10);
average(stu, 10);
high_score(stu, 10);
return 0;
}
void input(struct student s[], int n)
{
int i, j;
for (i=0; i<n; i++){
printf("Please enter No.%d student num name score: ", i+1);
scanf("%d %s", &s[i].num, s[i].name);
for (j=0; j<3; scanf("%f", &s[i].score[j++]));
}
}
void average(struct student s[], int n)
{
int i, j;
float sum;
for (i=0, sum=0.0; i<n; i++)
for (j=0; j<3; sum+=s[i].score[j++]);
printf("Average=%.2f\n", sum/n);
}
void high_score(struct student s[], int n)
{
int i, j;
float sum;
struct student temp;
for (i=0; i<n; i++){
for (j=0, sum=0.0; j<3; sum+=s[i].score[j++]);
s[i].aver=sum/3;
}
for (i=0; i<n; i++)
for (j=i+1; j<n; s[i].aver<s[j].aver ? temp=s[i], s[i]=s[j], s[j]=temp, j++ : j++);
printf("The highest student info: %d %-5s ", s[0].num, s[0].name);
for (i=0; i<3; printf("%.2f ", s[0].score[i++]));
printf("%.2f\n", s[0].aver);
}方法2：
#include <stdio.h>
#include <stdlib.h>
struct Student{
int num;
char name[20];
float score[3];
};
void input(Student *st);
void print(Student *st);
int main()
{
Student *stu=(Student*)malloc(3*sizeof(Student));
input(stu);
print(stu);
system("pause");
return 0;
}
void input(Student *st)
{
int i;
Student *p;
for (p=st, i=0; p<st+3; p++, i++){
printf("Please enter No.%d student info: ", i+1);
scanf("%d %s", &p->num, p->name);
for (i=0; i<3; scanf("%f", &p->score[i++]));
}
}
void print(Student *st)
{
int i, j;
float aver, sum[3], total, max;
Student *p;
for (p=st, i=0, total=0; p<st+3; p++, i++){
for (j=0, sum[i]=0; j<3; sum[i]+=p->score[j++]);
total+=sum[i]/3;
}
aver=total/3;
printf("Total Average: %.2f\n", aver);
for (i=0, max=sum[i]; i<3; i++)
if (sum[i]>max){
max=sum[i];
j=i;
}
printf("The highest score student info: %d %s ", (st+j)->num, (st+j)->name);
for (i=0; i<3; printf("%.2f ", (st+j)->score[i++]));
printf("\n");
}数组访问越界的问题
参考GPT的修改：
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
#define max_m 3 // 机器数
#define max_t 100 // 任务数上限
#define INF 1000
int n; // 实际任务数
int t_m[max_t][max_m]; // 存储机器与任务的矩阵
typedef struct Node {
int sum1;
int sum2;
int lb;
int t_num; // 已执行任务数
int t; // 当前任务
bool visited[max_t]; // 标记已执行任务
int es[max_t]; // 执行序列
bool operator< (const Node &p) const {
return p.lb < lb;
}
} Node;
priority_queue<Node> pp;
int up;
void get_up() { // 获取上界，任务从1到4按序执行
up = 0;
for(int i = 0; i < max_t; i++)
up += t_m[i][max_m-1];
for(int j = 0; j < max_m-1; j++)
up += t_m[0][j];
}
int get_lb(Node node) { // 获取目标函数值
node.lb = node.sum2;
int min = INF;
for(int i = 0; i < n; i++)
if(!node.visited[i]) {
if(i != node.t) {
if (i != node.t) {
node.lb += t_m[i][1]; // 加上剩余任务在第二个机器上完成时间和
} // 加上剩余任务在第二个机器上完成时间和
if(t_m[i][2] < min)
min = t_m[i][2];
}
}
node.lb += min; // 加上剩余任务中执行时间最短的一个
return node.lb;
}
void solve() {
get_up();
int sequence[max_t];
Node first; // 初始化第一个节点
first.t_num = 0;
first.lb = 0;
first.t = -1;
first.sum1 = 0;
first.sum2 = 0;
for(int i = 0; i < n; i++)
first.visited[i] = false;
for(int j = 0; j < n; j++)
first.es[j] = -1;
pp.push(first);
while(pp.size()) {
Node tmp= pp.top();
pp.pop();
if(tmp.t_num == n-1) {
int ans;
for(int i = 0; i < n; i++) {
sequence[i] = tmp.es[i];
if(!tmp.visited[i]) // 找到最后一个未执行任务
ans = i;
}
sequence[n-1] = ans;
break;
} else {
Node next;
for(int i = 0; i < n; i++)
next.visited[i] = false;
for(int i = 0; i < n; i++) {
if(!tmp.visited[i]) {
next.t_num = tmp.t_num + 1;
next.t = i;
for(int j = 0; j < n; j++) // 继承执行序列
next.es[j] = tmp.es[j];
next.es[next.t_num-1] = i;
next.sum1 = tmp.sum1 + t_m[i][0];
if(next.sum1 > tmp.sum2)
next.sum2 = next.sum1 + t_m[i][1];
else
next.sum2 = tmp.sum2 + t_m[i][1];
for(int j = 0; j < n; j++)
next.visited[j] = tmp.visited[j]; // 继承任务操作标记
next.visited[i] = true;
next.lb = get_lb(next);
if(next.lb <= up) {
pp.push(next);
}
}
}
}
}
printf("最优解任务执行序列为：");
for(int i = 0; i < n; i++) {
printf("%d ", sequence[i] + 1);
}
}
int main() {
printf("请输入任务数：");
scanf("%d", &n);
printf("请输入任务-机器矩阵：\n");
for(int i = 0; i < n; i++)
for(int j = 0; j < max_m; j++) {
scanf("%d", &t_m[i][j]);
if(j == max_m - 1)
getchar();
}
solve();
}
拿走不谢：
#include <stdio.h>
#include <stdlib.h>
// 定义工序耗时的结构体
typedef struct {
int time; // 工序耗时
int index; // 工序编号
} Task;
// 比较两个工序耗时的函数，返回值为负数表示第一个工序耗时更短，正数表示第二个工序耗时更短，0表示两者耗时相同
int compare_tasks(Task a, Task b) {
if (a.time == b.time) {
return 0;
} else if (a.time > b.time) {
return -1;
} else {
return 1;
}
}
// 将所有工序按照耗时从小到大排序的函数
void sort_tasks(Task tasks[], int n) {
qsort(tasks, n, sizeof(Task), compare_tasks);
}
// 工厂流水线工作安排算法的主函数
void factory_flow_schedule(Task tasks[], int n) {
int i, j;
for (i = 0; i < n; i++) {
printf("Processing product %d\n", i + 1);
for (j = 0; j < n; j++) {
if (tasks[j].index == i) { // 如果当前工序是第i个产品要完成的工序，则进行加工
printf("Processing task %d at time %d\n", j + 1, tasks[j].time);
break; // 跳出循环，继续处理下一个产品要完成的工序
}
}
}
}
int main() {
int n;
printf("Enter the number of products:");
scanf("%d", &n);
n = n >= 10 && n <= 30 ? n : 10; // 确保输入的n在10到30之间
int tasks[n][2]; // 存储每个产品的每道工序的耗时和工序编号
int i;
for (i = 0; i < n; i++) {
printf("Enter the time and index of task %d:", i + 1);
scanf("%d %d", &tasks[i][0], &tasks[i][1]); // 分别输入该工序的耗时和工序编号
}
sort_tasks(tasks, n); // 将所有工序按照耗时从小到大排序
factory_flow_schedule(tasks, n); // 按照排序后的工序列表进行生产加工
你的代码使用了一个固定大小的数组 t_m[max_t][max_m] 来存储任务与机器之间的矩阵，而 max_t 的值为 200，max_m 的值为 3。数组空间太大导致在处理较大输入时出现问题。当你输入的任务数超过 10 时，程序将会出现内存溢出的情况，从而导致运行错误。
建议你可以采用动态分配内存的方式，根据输入的任务数动态申请内存，避免数组过大导致内存溢出的情况发生。例如使用 vector 来存储任务与机器之间的矩阵，代码如下所示：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1000
int n; // 实际任务数
vector<vector<int>> t_m; // 存储机器与任务的矩阵
typedef struct Node {
int sum1;
int sum2;
int lb;
int t_num; // 已执行任务数
int t; // 当前任务
bool visited[max_t]; // 标记已执行任务
vector<int> es; // 执行序列
bool operator< (const Node &p) const {
return p.lb < lb;
}
} Node;
priority_queue<Node> pp;
int up;
void get_up() { // 获取上界，任务从1到4按序执行
up = 0;
for(int i = 0; i < n; i++)
up += t_m[i][max_m-1];
for(int j = 0; j < max_m-1; j++)
up += t_m[0][j];
}
int get_lb(Node node) { // 获取目标函数值
node.lb = node.sum2;
int min = INF;
for(int i = 0; i < n; i++)
if(!node.visited[i]) {
if(i != node.t) {
if (i != node.t) {
node.lb += t_m[i][1]; // 加上剩余任务在第二个机器上完成时间和
} // 加上剩余任务在第二个机器上完成时间和
if(t_m[i][2] < min)
min = t_m[i][2];
}
}
node.lb += min; // 加上剩余任务中执行时间最短的一个
return node.lb;
}
void solve() {
get_up();
vector<int> sequence(n);
Node first; // 初始化第一个节点
first.t_num = 0;
first.lb = 0;
first.t = -1;
first.sum1 = 0;
first.sum2 = 0;
for(int i = 0; i < n; i++)
first.visited[i] = false;
first.es.resize(n, -1);
pp.push(first);
while(pp.size()) {
Node tmp= pp.top();
pp.pop();
if(tmp.t_num == n-1) {
int ans;
for(int i = 0; i < n; i++) {
sequence[i] = tmp.es[i];
if(!tmp.visited[i]) // 找到最后一个未执行任务
ans = i;
}
sequence[n-1] = ans;
break;
} else {
Node next;
for(int i = 0; i < n; i++)
next.visited[i] = false;
for(int i = 0; i < n; i++) {
if(!tmp.visited[i]) {
next.t_num = tmp.t_num + 1;
next.t = i;
next.es = tmp.es;
next.es[next.t_num-1] = i;
next.sum1 = tmp.sum1 + t_m[i][0];
if(next.sum1 > tmp.sum2)
next.sum2 = next.sum1 + t_m[i][1];
else
next.sum2 = tmp.sum2 + t_m[i][1];
for(int j = 0; j < n; j++)
next.visited[j] = tmp.visited[j]; // 继承任务操作标记
next.visited[i] = true;
next.lb = get_lb(next);
if(next.lb <= up) {
pp.push(next);
}
}
}
}
}
printf("最优解任务执行序列为：");
for(int i = 0; i < n; i++) {
printf("%d ", sequence[i] + 1);
}
}
int main() {
printf("请输入任务数：");
scanf("%d", &n);
printf("请输入任务-机器矩阵：\n");
t_m.resize(n, vector<int>(max_m));
for(int i = 0; i < n; i++)
for(int j = 0; j < max_m; j++) {
scanf("%d", &t_m[i][j]);
if(j == max_m - 1)
getchar();
}
solve();
}
分两种情况：
1.n<=m：n个作业直接分配给m台机器
2.n>m:将n中作业中的m个时间最长的分配给m台机器，然后依次选其完成时间最早的机器继续执行剩余的作业，直到所有作业完成即可。
#include<stdio.h>
int t[200],d[200]; /*定义全局变量t,d*/
struct job{ /*定义结构体数组*/
int h;
int t;
}job[200],s[200];
void sort (int n){ /*定义函数sort()*/
int i;
for(i=1;i<=n;i++)
s[i]=job[i];
for(i=1;i<=n;i++) /*冒泡排序*/
for(int j=i+1;j<=n;j++){
if(s[i].t<s[j].t){
int k=s[i].t;
int w=s[i].h;
s[i].t=s[j].t;
s[i].h=s[j].h;
s[j].t=k;
s[j].h=w;
}
}
}
void fenpei(int a,int b){ /*定义函数fenpei()*/
int i,j,k,min,z;
for(i=1;i<=a;i++) /*初始化d[b]*/
d[i]=0;
for(i=1;i<=b;i++)
d[i]=s[i].t; /*放入最初的m个作业*/
for(i=b+1;i<=a;i++){ /*放入剩余作业*/
for(k=1;k<b;k++)
for(z=k+1;z<=b;z++) /*从机器中找出工作时间最小的作业*/
if(d[k]<d[z])
j=k;
else
j=z;
d[j]=d[j]+s[i].t;
} /*将剩余作业放入对应机器中*/
for(k=1;k<a;k++) /*求出最短工作时间*/
if(d[k]>d[k+1])
min=d[k];
printf("最短工作时间为:%d\n",min);
}
void main(){
int n,m,i;
printf("输入作业的个数及机器的台数:");
scanf("%d%d",&n,&m); /*键盘输入机器台数及作业个数*/
for(i=1;i<=n;i++){
scanf("%d",&t[i]); /*初始化每个作业的工作时间*/
job[i].h=i;
job[i].t=t[i];
}
for(i=1;i<=n;i++){
s[i].h=0;
s[i].t=0;
}
sort(n); /*调用sort()函数*/
fenpei(n,m); /*调用fenpei()函数求解问题*/
}