二分搜索 ¶
class Flowshop;
class MinHeapNode {
friend Flowshop;
public:
operator int() const { return bb; }
private:
void Init(int), NewNode(MinHeapNode, int, int, int, int);
int s, f1, f2, sf2, bb, *x;
};
void MinHeapNode::Init(int n) {
x = new int[n + 1];
for (int i = 1; i <= n; i++)
x[i] = 0;
s = 0;
f1 = 0;
f2 = 0;
sf2 = 0;
bb = 0;
}
void MinHeapNode::NewNode(MinHeapNode E, int Ef1, int Ef2, int Ebb, int n) {
x = new int[n];
for (int i = 0; i < n; i++)
x[i] = E.x[i];
f1 = Ef1;
f2 = Ef2;
sf2 = E.sf2 + f2;
bb = Ebb;
s = E.s + 1;
}
class Flowshop {
friend void main(void);
public:
int BBFlow(void);
private:
int Bound(MinHeapNode, int&, int&, bool**);
void Sort(void);
int n, **M, **b, **a, *bestx, bestc;
bool **y;
};
void Flowshop::Sort(void) {
int *c = new int[n];
for (int j = 0; j < 2; j++) {
for (int i = 0; i < n; i++) {
b[i][j] = M[i][j];
c[i] = i;
}
for (int i = 0; i < n - 1; i++) {
for (int k = n - 1; k > i; k--) {
if (b[k][j] < b[k - 1][j]) {
Swap(b[k][j], b[k - 1][j]);
Swap(c[k], c[k - 1]);
}
for (int i = 0; i < n; i++)
a[c[i]][j] = i;
}
}
}
delete[] c;
}
int Flowshop::Bound(MinHeapNode E, int& f1, int& f2, bool** y) {
for (int k = 0; k < n; k++) {
for (int j = 0; j < 2; j++) {
y[k][j] = false;
}
}
for (int k = 0; k <= E.s; k++) {
for (int j = 0; j < 2; j++) {
y[a[E.x[k]][j]][j] = true;
}
}
f1 = E.f1 + M[E.x[E.s]][0];
f2 = (f1 > E.f2 ? f1 : E.f2) + M[E.x[E.s]][1];
int sf2 = E.sf2 + f2;
int s1 = 0, s2 = 0, k1 = n - E.s, k2 = n - E.s, f3 = f2;
for (int j = 0; j < n; j++) {
if (!y[j][0]) {
k1--;
if (k1 == n - E.s - 1) {
f3 = (f2 > f1 + b[j][0]) ? f2 : f1 + b[j][0];
}
s1 += f1 + k1 * b[j][0];
}
}
for (int j = 0; j < n; j++) {
if (!y[j][1]) {
k2--;
s1 += b[j][1];
s2 += f3 + k2 * b[j][1];
}
}
return sf2 + (s1 < s2 ? s2 : s1);
}
int Flowshop::BBFlow(void) {
Sort();
MinHeap<MinHeapNode> H(1000);
MinHeapNode E;
E.Init(n);
while (E.s <= n) {
if (E.s == n) {
if (E.sf2 < bestc) {
bestc = E.sf2;
for (int i = 0; i < n; i++)
bestx[i] = E.x[i];
}
delete[] E.x;
} else {
for (int i = E.s; i < n; i++) {
Swap(E.x[E.s], E.x[i]);
int f1, f2;
int bb = Bound(E, f1, f2, y);
if (bb < bestc) {
MinHeapNode N;
N.NewNode(E, f1, f2, bb, n);
H.Insert(N);
}
Swap(E.x[E.s], E.x[i]);
}
delete[] E.x;
}
try {
H.DeleteMin(E);
} catch (OutOfBounds) {
break;
}
}
return bestc;
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42