/*
批处理作业调度
输入: 3
2 1
3 1
2 3
输出：18
1 3 2
*/
#include
#include
#include
#define MAXSIZE 100
int n; //作业的个数
int m1[MAXSIZE]; //每个作业在机器一上完成的时间
int m2[MAXSIZE]; //每个作业在机器二上完成的时间
int f1; //机器一完成的时间
int f2[MAXSIZE]; //机器二完成的时间
int cf; //当前所用时间
int bestf; //当前最优时间
int x[MAXSIZE]; //当前解
int bestx[MAXSIZE]; //最优解
//输入
void input();
//初始化
void init();
//回溯法
void backtrack(int);
//交换
void Swap(int*, int*);
int main(void)
{
int i = 1;
while (1)
{
input();
init();
backtrack(1);
printf("%d\n", bestf);
for (i = 1; i <= n; ++i)
{
printf("%d ", bestx[i]);
}
printf("\n");
}
return 0;
}
void input()
{
int i = 1;
printf("please enter n:");
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &m1[i], &m2[i]);
}
}
void init()
{
int i = 1;
cf = 0;
bestf = INT_MAX;
f1 = 0;
for (i = 1; i <= n; ++i)
{
x[i] = i;
f2[i] = 0;
}
}
void backtrack(int t)
{
int i = 1;
int j = 1;
if (t > n)
{
if (cf < bestf)
{
bestf = cf;
for (i = 1; i <= n; ++i)
{
bestx[i] = x[i];
}
}
}
else
{
for (j = t; j <= n; ++j)
{
f1 += m1[x[j]];
f2[t] = (f1 > f2[t - 1] ? f1 : f2[t - 1]) + m2[x[j]];
cf += f2[t];
if (cf < bestf)
{
Swap(&x[t], &x[j]);
backtrack(t + 1);
Swap(&x[t], &x[j]);
}
f1 -= m1[x[j]];
cf -= f2[t];
}
}
}
void Swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}