Algoritma tamak dan pelaksanaannya dalam C++

Algoritma tamak ialah idea algoritma yang biasa digunakan dan digunakan secara meluas dalam banyak masalah. Idea teras adalah untuk hanya mempertimbangkan penyelesaian optimum segera apabila membuat keputusan pada setiap langkah, tanpa mengambil kira kesan jangka panjang.

Dalam C++, pelaksanaan algoritma tamak selalunya melibatkan operasi asas seperti pengisihan dan pemprosesan data. Di bawah, kami akan memperkenalkan idea algoritma tamak dan pelaksanaannya dalam C++ untuk beberapa masalah biasa.

1. Masalah Penjadualan Aktiviti

Memandangkan satu set aktiviti, setiap aktiviti mempunyai masa mula dan masa tamat, dan seseorang hanya boleh mengambil bahagian dalam satu aktiviti pada satu masa. Tanya bagaimana untuk mengatur aktiviti untuk memastikan bahawa orang ini mengambil bahagian dalam bilangan maksimum aktiviti.

Idea algoritma tamak adalah untuk mengisih dahulu setiap aktiviti dalam tertib menaik menjelang masa tamat, dan kemudian bermula dari aktiviti pertama, pilih aktiviti dengan masa tamat paling awal sebagai aktiviti pertama untuk mengambil bahagian. Kemudian, pilih aktiviti dengan masa tamat paling awal yang serasi dengan aktiviti semasa daripada aktiviti yang tinggal dan jadikan aktiviti seterusnya untuk disertai. Ulangi proses ini sehingga semua aktiviti telah dijadualkan.

Berikut ialah pelaksanaan kod C++:

struct activity {
    int start;
    int end;
}

bool cmp(activity a, activity b) {
    return a.end < b.end;
}

int arrangeActivities(activity arr[], int n) {
    sort(arr, arr + n, cmp);
    int cnt = 1;
    int lastEnd = arr[0].end;
    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastEnd) {
            cnt++;
            lastEnd = arr[i].end;
        }
    }
    return cnt;
}

2. Masalah pengekodan Huffman

Memandangkan satu set nilai berat, ia diperlukan untuk mengekodnya ke dalam rentetan binari yang tidak sama panjang supaya panjang pengekodan jumlah semua nilai diminimumkan.

Idea ​​​algoritma tamak adalah untuk mengisih pemberat terlebih dahulu dalam tertib menaik, pilih dua nod dengan pemberat terkecil dalam setiap langkah untuk digabungkan menjadi nod baharu, dan tentukan beratnya sebagai jumlah pemberat daripada dua nod. Ulangi proses ini sehingga semua nod digabungkan menjadi nod akar. Pokok binari yang sepadan dengan nod akar ini ialah pokok Huffman. Apabila melintasi pokok Huffman, berjalan ke kiri bermakna menambah 0, dan berjalan ke kanan bermakna menambah 1. Dengan cara ini, pengekodan yang sepadan bagi setiap berat boleh diselesaikan.

Berikut ialah pelaksanaan kod C++:

struct Node {
    int weight;
    int parent, leftChild, rightChild;
}

bool cmp(Node a, Node b) {
    return a.weight < b.weight;
}

void buildHuffmanTree(Node arr[], int n) {
    // 初始化所有节点
    for (int i = 0; i < n; i++) {
        arr[i].parent = -1;
        arr[i].leftChild = -1;
        arr[i].rightChild = -1;
    }

    // 构建哈夫曼树
    for (int i = n; i < 2 * n - 1; i++) {
        int minIndex1 = -1, minIndex2 = -1;
        for (int j = 0; j < i; j++) {
            if (arr[j].parent == -1) {
                if (minIndex1 == -1) {
                    minIndex1 = j;
                }
                else if (minIndex2 == -1) {
                    minIndex2 = j;
                }
                else {
                    if (arr[j].weight < arr[minIndex1].weight) {
                        minIndex2 = minIndex1;
                        minIndex1 = j;
                    }
                    else if (arr[j].weight < arr[minIndex2].weight) {
                        minIndex2 = j;
                    }
                }
            }
        }
        arr[minIndex1].parent = i;
        arr[minIndex2].parent = i;
        arr[i].leftChild = minIndex1;
        arr[i].rightChild = minIndex2;
        arr[i].weight = arr[minIndex1].weight + arr[minIndex2].weight;
    }
}

void findHuffmanCode(Node arr[], int n) {
    // 从叶节点开始遍历哈夫曼树
    for (int i = 0; i < n; i++) {
        string code = "";
        int currentNode = i;
        while (arr[currentNode].parent != -1) {
            int parent = arr[currentNode].parent;
            if (arr[parent].leftChild == currentNode) {
                code = "0" + code;
            }
            else {
                code = "1" + code;
            }
            currentNode = parent;
        }
        cout << code << endl;
    }
}

3 Selesaikan masalah penukaran syiling

Memandangkan nilai muka set syiling dan jumlah perubahan yang perlu dibuat, tanya berapa banyak syiling yang diperlukan untuk membuat jumlah.

Idea ​​​algoritma tamak adalah untuk menyusun dahulu syiling dalam susunan menurun mengikut nilai muka, kemudian mulakan dengan syiling dengan nilai muka terbesar, teruskan mengambil syiling sehingga tiada lagi pilihan boleh dibuat, dan kemudian gunakan syiling dengan nilai muka terbesar seterusnya sehingga jumlah keseluruhan dikumpulkan.

Berikut ialah pelaksanaan kod C++:

bool cmp(int a, int b) {
    return a > b;
}

int minCoinNum(int coins[], int n, int amount) {
    sort(coins, coins + n, cmp);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (amount >= coins[i]) {
            cnt += amount / coins[i];
            amount -= coins[i] * (amount / coins[i]);
        }
    }
    return cnt;
}

Dalam proses pembangunan sebenar, algoritma tamak selalunya bukan penyelesaian yang optimum, tetapi kesederhanaan dan kecekapannya menjadikannya digunakan secara meluas. Melalui pengenalan tiga masalah tipikal di atas, saya percaya pembaca dapat lebih memahami dan menguasai idea algoritma tamak dan pelaksanaannya dalam C++.

Atas ialah kandungan terperinci Algoritma tamak dan pelaksanaannya dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!