电路板排列问题
class Board {
friend Arrangement(int **, int, int, int []);
private:
void Backtrack(int i, int cd);
int n, m, *x, *bestx, bestd, *total, *now, **B;
};
void Board::Backtrack(int i, int cd) {
if (i == n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestd = cd;
} else {
for (int j = i; j <= n; j++) {
int ld = 0;
for (int k = 1; k <= m; k++) {
now[k] += B[x[j]][k];
if (now[k] > 0 && total[k] != now[k]) {
ld++;
}
}
if (cd > ld) {
ld = cd;
}
if (ld < bestd) {
Swap(x[i], x[j]);
Backtrack(i + 1, ld);
Swap(x[i], x[j]);
}
for (int k = 1; k <= m; k++) {
now[k] -= B[x[j]][k];
}
}
}
}
int Arrangement(int **B, int n, int m, int bestx[]) {
Board X;
X.x = new int[n + 1];
X.total = new int[m + 1];
X.now = new int[m + 1];
X.B = B;
X.n = n;
X.m = m;
X.bestx = bestx;
X.bestd = m + 1;
for (int i = 1; i <= m; i++) {
X.total[i] = 0;
X.now[i] = 0;
}
for (int i = 1; i <= n; i++) {
X.x[i] = i;
for (int j = 1; j <= m; j++) {
X.total[j] += B[i][j];
}
}
X.Backtrack(1, 0);
delete [] X.x;
delete [] X.total;
delete [] X.now;
return X.bestd;
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 16:56:10
创建日期: 2024年1月2日 16:56:10