PTA算法测试题（函数）-创新互联

0/1背包问题（回溯法）
void dfs(int i,int tw,int tv,int rw,int op[]) {
if(i >n) {
if(tw == W && tv >maxv) {
 maxv = tv;
 for(int j = 1; j <= n; j ++ ) x[j] = op[j];
}
} else {
if(tw + w[i] <= W) {
 op[i] = 1;
 dfs(i + 1, tw + w[i], tv + v[i], rw - w[i], op);
}
op[i] = 0;
if(tw + rw >W) dfs(i + 1, tw, tv, rw - w[i], op);
}
}

快速排序（分治法）
int Partition(SqList &L,int low,int high) {
L.r[0] = L.r[low];
int t = L.r[low].key;

while(low < high) {
while(low < high && L.r[high].key >= t) high --;
L.r[low] = L.r[high];
while(low < high && L.r[low].key <= t) low ++ ;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;

}

void QSort(SqList &L,int low,int high) {
if(low < high) {
int t = Partition(L, low, high);
QSort(L, low, t - 1);
QSort(L, t + 1, high);
}

}

棋盘覆盖问题（分治法）
void ChessBoard(int tr,int tc,int dr,int dc,int size) {
if(size == 1) return;

int s = size / 2;
int t = tile ++;

if(dr < tr + s && dc < tc + s) ChessBoard(tr, tc, dr, dc, s);
else {
board[tr + s - 1][tc + s - 1] = t;
ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}

if(dr < tr + s && dc >= tc + s) ChessBoard(tr, tc + s, dr, dc, s);
else {
board[tr + s - 1][tc + s] = t;
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}

if(dr >= tr + s && dc < tc + s) ChessBoard(tr + s, tc, dr, dc, s);
else {
board[tr + s][tc + s - 1] = t;
ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}

if(dr >= tr + s && dc >= tc + s) ChessBoard(tr + s, tc + s, dr, dc, s);
else {
board[tr + s][tc + s] = t;
ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}

求解活动安排问题（贪心法）
void solve() {
sort(A, A + n);
int t = 0;
for(int i = 0; i < n; i ++ ) {
if(A[i].b >= t) {
 flag[i] = true;
 t = A[i].e;
}
}
}

最小生成树（克鲁斯卡尔算法）
int p[MVNum];

int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

void Kruskal(AMGraph G) {
for(int i = 0; i < G.vexnum; i ++ ) p[i] = i;

for(int k = 0; k < G.arcnum; k ++ ) {
int min = MaxInt, mini = MaxInt, minj = MaxInt;
for(int i = 0; i < G.vexnum; i ++ ) {
 for(int j = 0; j < G.vexnum; j ++ ) {
     if(G.arcs[i][j] < min) {
         min = G.arcs[i][j];
         mini = i;
         minj = j;
     }
 }
}
int pa = find(mini), pb = find(minj);
if(pa != pb) {
 p[pa] = pb;
 printf("%d->%d\n", mini, minj);
}
G.arcs[mini][minj] = G.arcs[minj][mini] = MaxInt;
}
}

求解最长递增子序列问题（动态规划法）
void IncreaseOrder(int a[],int dp[],int x[][N],int n) {
for(int i = 0; i < n; i ++ ) {
dp[i] = 1;
x[i][0] = a[i];

int max = 1, maxi = i;
for(int j = 0; j < i; j ++ ) {
 if(a[j] < a[i] && dp[j] + 1 >max) {
     max = dp[j] + 1;
     maxi = j;
 }
}

if(maxi != i) {
 dp[i] = max;
 for(int j = 0; j < max - 1; j ++ ) x[i][j] = x[maxi][j];
 x[i][max - 1] = a[i];
}
}
}

最短路径（弗洛伊德算法）
void ShortestPath_Floyed(AMGraph G){ 
int i , j , k ;
for (i = 0; i < G.vexnum; ++i)
for(j = 0; j < G.vexnum; ++j){ 
 D[i][j] = G.arcs[i][j];
 if(D[i][j] < MaxInt && i != j) Path[i][j] = i;
 else Path [i][j] = -1; 
}
for(k = 0; k < G.vexnum; ++k) 
for(i = 0; i < G.vexnum; ++i) 
 for(j = 0; j < G.vexnum; ++j)
     if(D[i][k] + D[k][j] < D[i][j]) {
         D[i][j] = D[i][k] + D[k][j];
         Path[i][j] = Path[k][j];
     }

}

求解图的m着色问题（回溯法）
void dfs(int i) {
if(i >n) count ++;
else {
for(int j = 1; j <= m; j ++ ) {
 x[i] = j;
 if(Same(i)) dfs(i + 1);
 x[i] = 0;
}
}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧