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元起，快前往官网查看详情吧
标题名称：PTA算法测试题（函数）-创新互联
路径分享：http://scjbc.cn/article/pihos.html
