我有一组船只(数据在外部 .txt 文件中给出:船只编号、到达时间、服务时间、到期时间、惩罚因素、等待因素)，它们来到泊位并一个接一个地服务。我需要找到成本最低的船只订单。我使用的是非常基本的方法——生成所有可能的序列，然后比较每个序列的成本。一个容器只能提供一次，这意味着顺序不能重复。 每艘新来船的成本包括等待成本(排队等候的时间)和惩罚成本(逾期靠泊的时间)。 目前，我有一个包含 10 个嵌套循环的程序，用于 10 个容器的集合。 代码
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<time.h>
void main()
{
FILE *f1;
int n = 10;/*The number of vessels*/
int arr[10];
int count = 0, s = 1;
int a, b, c, d, e, f, g, h, i, j;
int t[10];
int min;
int time[10];
struct vessel{
int name;/*the name of the vessel*/
int ar; /*arrival time*/
int ser; /*service time*/
int exp; /*due time*/
int df; /*delay factor*/
int wf; /*waiting factor*/
};
struct vessel x[10]; /* where number means the total number of vessels arriving*/
for (i = 0; i < n; i++)
{
s = s*(n-i) ;
}
printf("S is %d\n", s);/*The number of possible sequences. (n-1)! */
f1 = fopen("sample1.txt", "r");/*Read data from file*/
if (f1 == NULL){
printf("Can not open the file\n");
getch();
return 0;
}
for (i = 0; i < n; i++)
{
fscanf(f1, "%d, %d, %d, %d, %d, %d\n", &x[i].name, &x[i].ar, &x[i].ser, &x[i].exp, &x[i].df, &x[i].wf);
arr[i] = x[i].name;
}
/*f2 = fopen("results.txt", "w");*/
min = 9999999999;/*Set it to be big.*/
for (a = 0; a < n; a++)/*First step. Set time and cost.*/
{
t[a] = 0;/*As first vessel comes and goes, there are no penalt or waiting cost.*/
time[a] = x[a].ar + x[a].ser;/*The time vessel arrives + the service time.*/
for (b = 0; b < n; b++)/*LOOP START.*/
{
if (b != a)/*One vessel can be served only once.*/
{
time[b] = 0;
if (time[a] > x[b].ar)/*If vessel arrived during service time of the previous one*/
{
if ((time[a] + x[b].ser - x[b].exp) > 0)/*If the service of current vessel ends after the due time.*/
{
t[b] = t[a] + (time[a] - x[b].ar)*x[b].wf + (time[a] + x[b].ser - x[b].exp)*x[b].df;
}
else/*If the service ends before the due time.*/
{
t[b] = t[a] + (time[a] - x[b].ar)*x[b].wf;
}
time[b] = time[a] + x[b].ser;/*Update time. The time when the service of current vessel ends.*/
}
else/*If vessel arrives after the service time of the previous one.*/
{
t[b] = t[a] + 0;/*No penalty or waiting cost.*/
time[b] = x[b].ar + x[b].ser;/*Update time. Current vessel arrival time + its service time.*/
}
if (t[b] < min)/*Check if current cost is smaller than found minimum cost. If yes, continue. If not, go to the start of the loop. LOOP END.*/
{
for (c = 0; c < n; c++)
{
if (c != b && c != a)
{
time[c] = 0;
if (time[b] > x[c].ar)
{
if ((time[b] + x[c].ser - x[c].exp) > 0)
{
t[c] = t[b] + (time[b] - x[c].ar)*x[c].wf + (time[b] + x[c].ser - x[c].exp)*x[c].df;
}
else
{
t[c] = t[b] + (time[b] - x[c].ar)*x[c].wf;
}
time[c] = time[b] + x[c].ser;
}
else
{
t[c] = t[b] + 0;
time[c] = x[c].ar + x[c].ser;
}
if (t[c] < min)
{
for (d = 0; d < n; d++)
{
if (d != c && d != b && d != a)
{
time[d] = 0;
if (time[c] > x[d].ar)
{
if ((time[c] + x[d].ser - x[d].exp) > 0)
{
t[d] = t[c] + (time[c] - x[d].ar)*x[d].wf + (time[c] + x[d].ser - x[d].exp)*x[d].df;
}
else
{
t[d] = t[c] + (time[c] - x[d].ar)*x[d].wf;
}
time[d] = time[c] + x[d].ser;
}
else
{
t[d] = t[c] + 0;
time[d] = x[d].ar + x[d].ser;
}
if (t[d] < min)
{
for (e = 0; e < n; e++)
{
if (e != d && e != c && e != b && e != a)
{
time[e] = 0;
if (time[d] > x[e].ar)
{
if ((time[d] + x[e].ser - x[e].exp) > 0)
{
t[e] = t[d] + (time[d] - x[e].ar)*x[e].wf + (time[d] + x[e].ser - x[e].exp)*x[e].df;
}
else
{
t[e] = t[d] + (time[d] - x[e].ar)*x[e].wf;
}
time[e] = time[d] + x[e].ser;
}
else
{
t[e] = t[d] + 0;
time[e] = x[e].ar + x[e].ser;
}
if (t[e] < min)
{
for (f = 0; f < n; f++)
{
if (f != e && f != d && f != c && f != b && f != a)
{
time[f] = 0;
if (time[e] > x[f].ar)
{
if ((time[e] + x[f].ser - x[f].exp) > 0)
{
t[f] = t[e] + (time[e] - x[f].ar)*x[f].wf + (time[e] + x[f].ser - x[f].exp)*x[f].df;
}
else
{
t[f] = t[e] + (time[e] - x[f].ar)*x[f].wf;
}
time[f] = time[e] + x[f].ser;
}
else
{
t[f] = t[e] + 0;
time[f] = x[f].ar + x[f].ser;
}
if (t[f] < min)
{
for (g = 0; g < n; g++)
{
if (g != a && g != b && g != c && g != d && g != e && g != f)
{
time[g] = 0;
if (time[f] > x[g].ar)
{
if ((time[f] + x[g].ser - x[g].exp) > 0)
{
t[g] = t[f] + (time[f] - x[g].ar)*x[g].wf + (time[f] + x[g].ser - x[g].exp)*x[g].df;
}
else
{
t[g] = t[f] + (time[f] - x[g].ar)*x[g].wf;
}
time[g] = time[f] + x[g].ser;
}
else
{
t[g] = t[f] + 0;
time[g] = x[g].ar + x[g].ser;
}
if (t[g] < min)
{
for (h = 0; h < n; h++)
{
if (h != a && h != b && h != c && h != d && h != e && h != f && h != g)
{
time[h] = 0;
if (time[g] > x[h].ar)
{
if ((time[g] + x[h].ser - x[h].exp) > 0)
{
t[h] = t[g] + (time[g] - x[h].ar)*x[h].wf + (time[g] + x[h].ser - x[h].exp)*x[h].df;
}
else
{
t[h] = t[g] + (time[g] - x[h].ar)*x[h].wf;
}
time[h] = time[g] + x[h].ser;
}
else
{
t[h] = t[g] + 0;
time[h] = x[h].ar + x[h].ser;
}
if (t[h] < min)
{
for (i = 0; i < n; i++)
{
if (i != a && i != b && i != c && i != d && i != e && i != f && i != g && i != h)
{
time[i] = 0;
if (time[h] > x[i].ar)
{
if ((time[h] + x[i].ser - x[i].exp) > 0)
{
t[i] = t[h] + (time[h] - x[i].ar)*x[i].wf + (time[h] + x[i].ser - x[i].exp)*x[i].df;
}
else
{
t[i] = t[h] + (time[h] - x[i].ar)*x[i].wf;
}
time[i] = time[h] + x[i].ser;
}
else
{
t[i] = t[h] + 0;
time[i] = x[i].ar + x[i].ser;
}
if (t[i] < min)
{
for (j = 0; j < n; j++)
{
if (j != a && j != b && j != c && j != d && j != e && j != f && j != g && j != h && j != i)
{
time[j] = 0;
if (time[i] > x[j].ar)
{
if ((time[i] + x[j].ser - x[j].exp) > 0)
{
t[j] = t[i] + (time[i] - x[j].ar)*x[j].wf + (time[i] + x[j].ser - x[j].exp)*x[j].df;
}
else
{
t[j] = t[i] + (time[i] - x[j].ar)*x[j].wf;
}
time[j] = time[i] + x[j].ser;
}
else
{
t[j] = t[i] + 0;
time[j] = x[j].ar + x[j].ser;
}
if (t[j] < min)
{
min = t[j];
printf("%d\n", min);
/*printf("%d %d %d %d %d %d %d %d %d %d\n", t[a], t[b], t[c], t[d], t[e], t[f], t[g], t[h], t[i], t[j]);*/
arr[0] = a + 1; arr[1] = b + 1; arr[2] = c + 1; arr[3] = d + 1; arr[4] = e + 1; arr[5] = f + 1; arr[6] = g + 1; arr[7] = h + 1; arr[8] = i + 1; arr[9] = j + 1;
}
count++;/*How many sequences of n vessels were able to reach the end of loop.*/
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
printf("Final sequence is: ");
for (i = 0; i < n; i++)
{
printf("%d, ", arr[i]);
}
printf("\nFinal count is %d\n", count);
printf("Final cost is %d\n", min);
getch();
return 0;
}
此代码有效。但。 它又长又讨厌。我不知道如何改变它。 对我来说唯一重要的部分是循环。 示例数据(以防万一)
1, 756, 207, 1148, 1160, 303
2, 660, 243, 1105, 847, 344
3, 1444, 225, 1857, 1006, 310
4, 1554, 199, 1941, 1004, 326
5, 1376, 186, 1737, 1112, 321
6, 1396, 170, 1680, 1053, 247
7, 1577, 158, 1917, 1005, 275
8, 629, 218, 1026, 976, 289
9, 807, 181, 1151, 1078, 299
10, 779, 157, 1088, 804, 254
非常感谢您的宝贵时间。
最佳答案
正如其他评论者已经指出的那样，递归是解决问题的好方法。我已经编写了一个可行的解决方案，请参见下文。我已将船舶的当前和(当前)最佳订单打包到 vessel 结构中。原始解决方案使用单独的数组。
order 条目还用作船舶是否已维修的指示符。零表示在等待队列中或尚未到达，正数表示船的订单。此值在递归更深之前设置并在之后重置。
在递归函数中，n 是(常数)容器数，m 是已服务的容器数。这允许快速检查我们是否完成。否则，m 必须在 service 的开头使用附加循环来确定。
当前最小值通过指针传递给递归函数。全局变量也可以工作，但我认为所有内容都在 service 本地的“封闭”解决方案更清晰。
此解决方案可扩展到超过 10 个容器。 (我得到的订单和你一样，但成本不同，所以我的解决方案在计算成本时有错误。我将把它留作练习，yadda，yadda ... 原则上，虽然代码似乎有效。)
#include <stdlib.h>
#include <stdio.h>
typedef struct Vessel Vessel;
struct Vessel {
int id;
int arrival;
int service;
int due;
int delay_cost;
int waiting_cost;
int order; /* Current order, 0 means not yet treated */
int final; /* final (optimum) order */
};
void service(Vessel *vessel, int n, int m, int time, int cost, int *min)
{
int i;
if (cost > *min) return;
if (m == n) {
while (n--) vessel[n].final = vessel[n].order;
*min = cost;
return;
}
for (i = 0; i < n; i++) {
Vessel *v = vessel + i;
int dtime = v->service;
int dcost = 0;
if (v->order) continue;
if (m == 0) {
time = v->arrival;
} else {
if (time < v->arrival) {
dtime += v->arrival - time;
dcost += (v->arrival - time) * v->waiting_cost;
}
}
if (time + dtime > v->due) {
dcost += v->delay_cost * (time + dtime - v->due);
}
v->order = m + 1;
service(vessel, n, m + 1, time + dtime, cost + dcost, min);
v->order = 0;
}
}
int vessel_cmp(const void *aa, const void *bb)
{
const Vessel *a = aa;
const Vessel *b = bb;
return a->final - b->final;
}
int main()
{
Vessel vessel[] = {
{1, 756, 207, 1148, 1160, 303, 0, 0},
{2, 660, 243, 1105, 847, 344, 0, 0},
{3, 1444, 225, 1857, 1006, 310, 0, 0},
{4, 1554, 199, 1941, 1004, 326, 0, 0},
{5, 1376, 186, 1737, 1112, 321, 0, 0},
{6, 1396, 170, 1680, 1053, 247, 0, 0},
{7, 1577, 158, 1917, 1005, 275, 0, 0},
{8, 629, 218, 1026, 976, 289, 0, 0},
{9, 807, 181, 1151, 1078, 299, 0, 0},
{10, 779, 157, 1088, 804, 254, 0, 0},
};
int nvessel = 10;
int min = 0x7fffffff;
int i;
service(vessel, nvessel, 0, 0, 0, &min);
qsort(vessel, nvessel, sizeof(vessel[0]), vessel_cmp);
printf("Final order: ");
for (i = 0; i < nvessel; i++) {
if (i) printf(", ");
printf("%d", vessel[i].id);
}
printf("\n");
printf("Total cost: %d\n", min);
return 0;
}
关于c - 如何摆脱嵌套循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20131084/