c++语言 动态规划法、贪心算法和回朔法和分支限界法四种方法分别实现对下面问题的求解 题目：某厂为扩大生产能力，拟订购某种成套4—6套，以分配给其所辖1、2、3个分厂使用。预计某个分厂分得不同套数的设备后，每年创造的利润（万元）如下表所示。该厂应订购几套设备并如何分配，才能使每年预计创利总额最大？ 分厂 利润（万元） 0套 1套 2套 3套 4套 5套 6套 1 0 3 5 6 7 6 5 2 0 4 6 7 8 9 10 3 0 2 5 9 8 8 7

以下是四种算法的实现：

1. 动态规划法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 3, M = 7;
int f[M], g[M];
int w[N + 1][M] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 3, 5, 6, 7, 6, 5},
    {0, 4, 6, 7, 8, 9, 10},
    {0, 2, 5, 9, 8, 8, 7}
};

int main() {
    for (int i = 1; i <= N; i++) {
        for (int j = 4; j <= M; j++) {
            for (int k = 0; k <= j; k++) {
                g[k] = f[j - k] + w[i][k];
            }
            f[j] = *max_element(g, g + j + 1);
        }
    }
    cout << f[M] << endl;
    return 0;
}

2. 贪心算法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 3, M = 7;
int w[N + 1][M] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 3, 5, 6, 7, 6, 5},
    {0, 4, 6, 7, 8, 9, 10},
    {0, 2, 5, 9, 8, 8, 7}
};

struct Item {
    int profit, count;
    bool operator<(const Item& other) const {
        return profit > other.profit;
    }
};

int main() {
    Item items[M - 4];
    for (int i = 0; i <= M - 4; i++) {
        int total = 0;
        for (int j = 1; j <= N; j++) {
            total += w[j][i];
        }
        items[i] = {total, i};
    }
    sort(items, items + M - 4);
    int ans = 0;
    for (int i = 0, cnt = 0; i < M - 4 && cnt < N; i++) {
        int count = min(M - items[i].count, 6);
        ans += items[i].profit * count;
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

3. 回溯法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 3, M = 7;
int w[N + 1][M] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 3, 5, 6, 7, 6, 5},
    {0, 4, 6, 7, 8, 9, 10},
    {0, 2, 5, 9, 8, 8, 7}
};
int ans = 0;

void dfs(int depth, int sum, int cnt[]) {
    if (depth == N + 1) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i <= 6; i++) {
        if (cnt[i] == 0) continue;
        cnt[i]--;
        dfs(depth + 1, sum + w[depth][i], cnt);
        cnt[i]++;
    }
}

int main() {
    int cnt[7] = {0, 0, 0, 1, 1, 1, 0};
    dfs(1, 0, cnt);
    cout << ans << endl;
    return 0;
}

4. 分支限界法

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 3, M = 7;
int w[N + 1][M] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 3, 5, 6, 7, 6, 5},
    {0, 4, 6, 7, 8, 9, 10},
    {0, 2, 5, 9, 8, 8, 7}
};

struct Node {
    int depth, sum, count[M];
    bool operator<(const Node& other) const {
        return sum < other.sum;
    }
};

int main() {
    priority_queue<Node> q;
    q.push({0, 0, {0, 0, 0, 1, 1, 1, 0}});
    int ans = 0;
    while (!q.empty()) {
        auto node = q.top();
        q.pop();
        if (node.depth == N + 1) {
            ans = node.sum;
            break;
        }
        for (int i = 0; i <= 6; i++) {
            if (node.count[i] == 0) continue;
            int count[M];
            copy(node.count, node.count + M, count);
            count[i]--;
            q.push({node.depth + 1, node.sum + w[node.depth][i], count});
        }
    }
    cout << ans << endl;
    return 0;
}