Giải thuật kinh điển với C++

Các giải thuật kinh điển nhất như Brute force, Backtracking...

Bài toán cái túi - Knapsack

Bài toán cái túi - Knapsack - Nhánh cận với tìm kiếm dựa trên giá trị tốt nhất.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
#include <bits/stdc++.h> #include <iostream> using namespace std; struct item { float weight; int value; int index; }; struct node { int level, profit, bound; float weight; }; bool cmp(item a, item b) { double r1 = (double)a.value / a.weight; double r2 = (double)b.value / b.weight; return r1 > r2; } int bound(node u, int n, int W, item arr[]) { if (u.weight >= W) return 0; int profit_bound = u.profit; int j = u.level + 1; int totWeight = u.weight; while ((j < n) && (totWeight + arr[j].weight <= W)) { totWeight += arr[j].weight; profit_bound += arr[j].value; j++; } if (j < n) profit_bound += (W - totWeight) * arr[j].value / arr[j].weight; return profit_bound; } int knapsack(int W, item arr[], int n) { sort(arr, arr + n, cmp); queue<node> Q; node u, v; u.level = -1; u.profit = u.weight = 0; Q.push(u); int maxProfit = 0; while (!Q.empty()) { u = Q.front(); Q.pop(); if (u.level == -1) v.level = 0; if (u.level == n-1) continue; v.level = u.level + 1; v.weight = u.weight + arr[v.level].weight; v.profit = u.profit + arr[v.level].value; if (v.weight <= W && v.profit > maxProfit) { maxProfit = v.profit; cout << arr[v.level].index << " "; } v.bound = bound(v, n, W, arr); if (v.bound > maxProfit) Q.push(v); v.weight = u.weight; v.profit = u.profit; v.bound = bound(v, n, W, arr); if (v.bound > maxProfit) Q.push(v); } return maxProfit; } int W, n; int main() { cin >> W; cin >> n; item arr[100]; for (int i = 0; i < n; i++) { cin >> arr[i].weight >> arr[i].value; arr[i].index = i + 1; } cout << endl << knapsack(W, arr, n); return 0; }

Bài toán người đi bán hàng - Brute force

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
#include <iostream> #include <vector> using namespace std; #define INF 9999999999999 vector<int> ans; int ansWeight = INF; bool checkPath(int a[], int n) { for (int i = 0; i < n - 1; i++) if (graph[a[i]][a[i+1]] == INF) return false; if (graph[a[n-1]][a[0]] == INF) return false; return true; } void hoanvi(int pivot, int a[], int n) { if (pivot == n) { if (checkPath(a, n) == false) return; int tempWeight = 0; vector<int> tempPath; for (int i = 0; i < n-1; i++) { tempWeight += graph[a[i]][a[i+1]]; tempAnsPath.push_back(a[i]); } tempWeight += graph[a[n-1]][a[0]]; if (tempWeight < ansWeight) { ansWeight = tempWeight; ansPath = tempPath; } } else { for (int i = pivot; i < n; i++) { swap(a[pivot], a[i]); hoanvi(pivot + 1, a, n); swap(a[pivot], a[i]); } } } int main() { cin >> n; int u, v, w(); cin >> u; while (u != -1) { cin >> v >> w; graph[u][v] = graph[v][u] = w; cin >> u; } int a[10000]; for (int i = 1; i <= n; i++) a[i] = i; hoanvi(0, a, n); return 0; }

Bài toán túi xách 0-1 - Brute force

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
#include <stdio.h> #include <iostream> #include <vector> using namespace std; int n, weight; bool a[100]; int ansWeight = 0, ansValue = 0; vector<int> ansSelection; void checkAns(int w[], int v[], int n) { int tempWeight = 0; int tempValue = 0; vector<int> tempSelection; for (int i = 0; i < n; i++) if (a[i]) { tempWeight += w[i]; tempValue += v[i]; tempSelection.push_back(i); if (tempWeight > weight) return; } if (tempWeight <= weight && tempValue > ansValue) { ansValue = tempValue; ansSelection = tempSelection; } } void backtrack(int u, int n, int w[], int v[]) { if (u == n) { checkAns(w, v, n); return; } a[u] = 0; backtrack(u + 1, n, w, v); a[u] = 1; backtrack(u + 1, n, w, v); } int main() { cin >> weight >> n; for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; backtrack(0, 5, w, v); for (int i = 0; i < ansSelection.size(); i++) { cout << ansSelection[i] << " "; } cout << endl << ansValue << endl; return 0; }

Bài toán người du lịch - Chu trình Hamilton

Bài toán người du lịch - Chu trình Hamilton - Backtracking.

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
#include <iostream> #include <cstring> using namespace std; #define N 100 #define INF 999999999 int G[N][N]; int path[N]; int n = 4; int ansWeight = INF; int ansPath[N]; bool promising(int pos, int v) { if (pos == n && G[v][path[1]] == 0) return false; else if (G[path[pos-1]][v] == 0) return false; else for (int i = 1; i < pos; i++) if (path[i] == v) return false; return true; } void Hamiltonian(int path[], int pos) { if (pos == n + 1) { int tempWeight = 0; for (int i = 1; i < n; i++) tempWeight += G[path[i]][path[i+1]]; tempWeight += G[path[n]][path[1]]; if (tempWeight < ansWeight) { ansWeight = tempWeight; for (int i = 1; i <= n; i++) ansPath[i] = path[i]; ansPath[n+1] = path[1]; } } else { for (int v = 1; v <= n; v++) { if (promising(pos, v)) { path[pos] = v; Hamiltonian(path, pos + 1); } } } } int main() { cin >> n; int u, v, w; cin >> u; while (u != -1) { cin >> v >> w; G[u][v] = G[v][u] = w; cin >> u; } memset(path, 0, sizeof(path)); Hamiltonian(path, 2); for (int i = 1; i <= n + 1; i++) cout << ansPath[i] << " "; cout << ansWeight << endl; return 0; }

Bài toán tìm đa giác lồi - Brute force mở rộng

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
#include <iostream> #include <math.h> #include <vector> #include <utility> #include <algorithm> using namespace std; #define PI 3.14159 struct Point { int x; int y; }; double computeAngle(Point from, Point to){ double angle = atan2(to.y - from.y, to.x - from.x); if (angle < 0) angle += 2 * PI; return angle; } pair<Point, double> findNextExtremePoint(vector<Point> poly, Point cur, double curAngle){ double minAngle = 2 * PI; Point next; for (int i = 0; i < poly.size(); i++) { if (poly[i].x == cur.x && poly[i].y == cur.y) continue; double angle = computeAngle(cur, poly[i]); if (angle < minAngle && angle >= curAngle) { next = poly[i]; minAngle = angle; } } return make_pair(next, minAngle); } vector<Point> computeConvexHull(vector<Point> poly){ vector <Point> convexHull; convexHull.push_back(poly[0]); double curAngle = 0; Point cur = poly[0]; while(true){ pair<Point, double> temp = findNextExtremePoint(poly, cur, curAngle); curAngle = temp.second; if (poly[0].x == temp.first.x && poly[0].y == temp.first.y) { break; } convexHull.push_back(temp.first); cur = temp.first; } return convexHull; } bool cmp(Point q, Point p){ return (q.x < p.x || (q.x == p.x && q.y < p.y)); } int main(){ cin >> n; vector <Point> poly; for (int i = 0; i < n; i++) { Point temp; cin >> temp.x >> temp.y; poly.push_back(temp); } sort(poly.begin(), poly.end(), cmp); vector<Point> ans; ans = computeConvexHull(poly); for (int i = 0; i < ans.size(); i++) cout << "(" << ans[i].x << "," << ans[i].y << ") "; return 0; }

Bài toán tìm dãy con tổng t - Backtracking

1234567891011121314151617181920212223242526272829303132333435363738394041424344
#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define N 100 bool s[N]; int w[N]; int n, total, t; void SoS(int k, int sum, int total, int w[], bool s[]) { if (sum == t) { for (int i = 1; i <= n; i++) cout << s[i] << " "; return; } else if ((sum + total >= t) && (sum + w[k] <= t)) { s[k] = true; SoS(k+1, sum + w[k], total - w[k], w, s); s[k] = false; SoS(k+1, sum, total - w[k], w, s); } } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> w[i]; cin >> t; memset(s, false, sizeof(s)); for (int i = 1; i <= n; i++) total += w[i]; sort(w + 1, w + n + 1); if (w[1] <= t && t <= total) { SoS(1, 0, total, w, s); } return 0; }

Bài toán đổi tiền xu - Brute force

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; int k, *coin; bool canChange = false; int minCoin(int arr[], int sum, int trace[]) { if (sum == 0){ if (canChange == false){ for (int i = 0 ; i < k; i++) { cout << arr[i] << ": " << trace[i] << endl; canChange = true; } return 0; } int res = 99999999; for (int i = 0; i < k; i++) { if (arr[i] <= sum) { trace[i]++; int temp = minCoin(arr, sum-arr[i], trace) + 1; if (res > temp) { res = temp; }; trace[i]--; } } return res; } int main() { int temp = 0, sum = 0; while (temp != 1) { cin >> temp; k++; coin = (int*) realloc(coin, sizeof(int) * k); coin[k - 1] = temp; } int* trace = (int*)malloc(sizeof(int) * k); cin >> sum; cout << minCoin(coin, sum, trace); delete coin; return 0; }

Bài toán mã đi tuần - Backtracking

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
#include <iostream> using namespace std; int row[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int col[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int h[100][100]; int res[10000][20][20]; int r0, c0, n, resNum; void KnightTour(int i, int r, int c) { for (int k = 0; k < 8; k++) { int u = r + row[k]; int v = c + col[k]; if (u < 1 || u > n) continue; if (v < 1 || v > n) continue; if (h[u][v] == 0) { h[u][v] = i; if (i == n*n) { resNum++; for (int a = 1; a <= n; a++){ for (int b = 1; b <= n; b++){ res[resNum][a][b] = h[a][b]; } } } else { KnightTour(i + 1, u, v); } h[u][v] = 0; } } } int main() { cin >> n; for (int r0 = 1; r0 <= n; r0++) { for (int c0 = 1; c0 <= n; c0++){ h[r0][c0] = 1; resNum = 0; KnightTour(2, r0, c0); cout << resNum << endl; for (int k = 1; k <= resNum; k++){ for (int i = 1; i <= n*n; i++){ int kt = 0; for (int a = 1; a <= n && kt == 0; a++){ for (int b = 1; b <= n && kt == 0; b++){ if(res[k][a][b] == i) { cout << "(" << a <<","<< b<< "),"; kt = 1; break; } } } } } } } return 0; }

Bài toán N quân hậu - Backtracking

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
#include <iostream> #include <utility> #include <vector> using namespace std; int n, numOfSolutions; int col[100]; vector<pair<int, int>> solutions[100]; bool promising(int i) { int j = 1; bool flag = true; while (j < i && flag) { if (col[i] == col[j] || abs(col[i] - col[j]) == i - j) flag = false; j++; } return flag; } void n_Queens(int i) { for (int j = 1; j <= n; j++) { col[i] = j; if (promising(i)) { if (i == n) { for (int k = 1; k <= n; k++) solutions[numOfSolutions].push_back(make_pair(k, col[k])); numOfSolutions++; } else { n_Queens(i + 1); } } } } int main() { cin >> n; n_Queens(1); cout << numOfSolutions << endl; for (int i = 0; i < numOfSolutions; i++) { for (int j = 0; j < solutions[i].size(); j++) cout << "(" << solutions[i][j].first << "," << solutions[i][j].second << "), "; cout << endl; } return 0; }

Bài toán tìm tổng dãy con liên tục - Brute force

1234567891011121314151617181920212223242526272829303132333435363738394041424344
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; double MaxContSubSum(double arr[], int numberOfElements, int &leftIndex, int &rightIndex) { double maxSum = 0, curSum = 0; leftIndex = rightIndex = 0; for (int j = 0; j < numberOfElements; j++) { curSum += arr[j]; if (curSum > maxSum) maxSum = curSum, rightIndex = j; else if (curSum < 0) curSum = 0, leftIndex = rightIndex = j + 1; } return maxSum; } int main() { int numberOfElements, leftIndex, rightIndex; float maxSum = 0; cin >> numberOfElements; double *arr = (double*) malloc(numberOfElements*sizeof(double)); for (int index = 0 ; index < numberOfElements; index++){ cin >> arr[index]; } maxSum = MaxContSubSum(arr, numberOfElements, leftIndex, rightIndex); if (leftIndex > -1 && rightIndex < numberOfElements) { for (int i = leftIndex; i <= rightIndex; i++) cout << fixed << setprecision(1) << arr[i] << " "; cout << endl; } cout << fixed << setprecision(1) << maxSum; delete arr; return 0; }