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;
}