- 技术
- 贪心法求解多机调度问题c++
#include<iostream>
using namespace std
;
int t
[7][2] = { 2,1,14,2,4,3,16,4,6,5,5,6,3,7 }, d
[3] = {0,0,0};
void MultiMachine(int t
[7][2], int n
, int d
[3], int m
)
{
int S
[3][7];
int rear
[3];
int i
, j
, k
;
for (i
= 0; i
< m
; i
++)
{
S
[i
][0] = t
[i
][1];
rear
[i
] = 0;
d
[i
] = t
[i
][0];
}
for (i
= m
; i
< n
; i
++)
{
for (j
= 0, k
= 1; k
< m
; k
++)
if (d
[k
] < d
[j
])
j
= k
;
rear
[j
]++;
S
[j
][rear
[j
]] = t
[i
][1];
d
[j
] = d
[j
] + t
[i
][0];
}
for (i
= 0; i
< m
; i
++)
{
cout
<< "机器" << i
+ 1 << ":";
for (j
= 0; S
[i
][j
] >= 0; j
++)
cout
<< "作业" << S
[i
][j
] << " ";
cout
<< endl
;
}
}
int Partition(int t
[7][2], int first
, int end
)
{
int i
= first
, j
= end
;
int temp1
, temp2
;
while (i
< j
)
{
while (i
< j
&&t
[i
][0] >= t
[j
][0]) j
--;
if (i
< j
)
{
temp1
= t
[i
][0]; temp2
= t
[i
][1];
t
[i
][0] = t
[j
][0]; t
[i
][1] = t
[j
][1];
t
[j
][0] = temp1
; t
[j
][1] = temp2
;
i
++;
}
while (i
< j
&&t
[i
][0] >= t
[j
][0]) i
++;
if (i
< j
)
{
temp1
= t
[i
][0]; temp2
= t
[i
][1];
t
[i
][0] = t
[j
][0]; t
[i
][1] = t
[j
][1];
t
[j
][0] = temp1
; t
[j
][1] = temp2
;
j
--;
}
}
return i
;
}
void Quicksort(int t
[7][2], int first
, int end
)
{
int pivot
;
if (first
< end
)
{
pivot
= Partition(t
, first
, end
);
Quicksort(t
, first
, pivot
- 1);
Quicksort(t
, pivot
+ 1, end
);
}
}
int main()
{
Quicksort(t
, 0, 6);
MultiMachine(t
, 7, d
, 3);
getchar();
getchar();
return 0;
}
Processed:
0.019, SQL:
9
