项目分配优化问题：贪心、动态规划和分支限界算法的应用

问题描述： 假设某公司有 n 个项目需要开展，每个项目的利润不同，需要一定的员工和时间去完成。公司有 m 个员工，每个员工的工作效率不同。请设计一个方案，使得公司利润最大化。

算法选择：

贪心算法： 考虑按照每个项目的单位利润排序，优先选择单位利润高的项目。如果某个项目需要的员工数超过了公司现有的员工数，就跳过该项目。
动态规划算法： 设 dp[i][j] 表示前 i 个项目，用 j 个员工可以达到的最大利润。则有状态转移方程：dp[i][j] = max(dp[i-1][j-k]+profit[i][k]), 其中 profit[i][k] 表示第 i 个项目用 k 个员工可以获得的利润。
分支限界算法： 设当前已经完成了前 k 个项目，用了 j 个员工，当前已获得的利润为 p。对于第 k+1 个项目，有两种选择：选或者不选。如果选了第 k+1 个项目，则员工数增加，利润增加，继续搜索；如果不选，则直接跳到第 k+2 个项目。

算法分析：

贪心算法 的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。但是贪心算法不能保证获得最优解，可能会出现选错项目的情况。
动态规划算法 的时间复杂度为 O(nm^2)，空间复杂度为 O(nm)。但是动态规划算法能够保证获得最优解，而且可以输出方案。
分支限界算法 的时间复杂度取决于搜索过程中的剪枝效果，最坏情况下时间复杂度为指数级别。空间复杂度为 O(n)。

未使用的算法：

蛮力法： 枚举所有可能的方案，选择最优解。时间复杂度为指数级别，不适用于本问题。
回溯法： 类似于分支限界算法，但是回溯法不进行剪枝，容易超时。不适用于本问题。
分治法： 将问题分成若干子问题，然后分别求解。本问题不适用于分治法，因为子问题之间存在相互关联。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1005
#define MAXM 105

int n, m;
int profit[MAXN], worker[MAXN];
int dp[MAXM][MAXN], choice[MAXM][MAXN];

// 贪心算法
int cmp(const void* a, const void* b) {
    return profit[*(int*)b] - profit[*(int*)a];
}

int greedy() {
    int ans = 0;
    int idx[MAXN];
    for (int i = 1; i <= n; i++) {
        idx[i] = i;
    }
    qsort(idx+1, n, sizeof(int), cmp);
    for (int i = 1; i <= n; i++) {
        int j = worker[idx[i]];
        if (j <= m) {
            ans += profit[idx[i]];
            m -= j;
        } else {
            break;
        }
    }
    return ans;
}

// 动态规划算法
int dynamic() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= j; k++) {
                if (worker[i] <= k) {
                    int t = dp[j-k][i-1] + profit[i]*k;
                    if (t > dp[j][i]) {
                        dp[j][i] = t;
                        choice[j][i] = k;
                    }
                }
            }
        }
    }
    return dp[m][n];
}

void print(int j, int i) {
    if (i == 0) {
        return;
    }
    if (choice[j][i] == 0) {
        print(j, i-1);
    } else {
        print(j-choice[j][i], i-1);
        printf('%d ', i);
    }
}

// 分支限界算法
typedef struct Node {
    int k, j, p;
} Node;

int cmp_node(const void* a, const void* b) {
    Node* na = (Node*)a;
    Node* nb = (Node*)b;
    return nb->p - na->p;
}

int bound(int k, int j, int p) {
    int ans = p;
    int idx[MAXN];
    for (int i = k+1; i <= n; i++) {
        idx[i] = i;
    }
    qsort(idx+k+1, n-k, sizeof(int), cmp);
    for (int i = k+1; i <= n && j >= worker[idx[i]]; i++) {
        j -= worker[idx[i]];
        ans += profit[idx[i]];
    }
    if (j > 0 && k < n) {
        ans += (int)((double)j*profit[idx[k+1]]/worker[idx[k+1]]);
    }
    return ans;
}

int branch() {
    int ans = 0;
    Node queue[MAXN*MAXM];
    int head = 0, tail = 0;
    queue[tail++] = (Node){0, m, 0};
    while (head != tail) {
        Node node = queue[head++];
        if (node.k == n) {
            if (node.p > ans) {
                ans = node.p;
            }
            continue;
        }
        if (node.j >= worker[node.k+1]) {
            queue[tail++] = (Node){node.k+1, node.j-worker[node.k+1], node.p+profit[node.k+1]};
        }
        int b = bound(node.k, node.j, node.p);
        if (b > ans) {
            queue[tail++] = (Node){node.k+1, node.j, node.p};
        }
    }
    return ans;
}

int main() {
    scanf('%d%d', &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf('%d%d', &profit[i], &worker[i]);
    }
    printf('贪心算法：\n');
    printf('%d\n', greedy());
    printf('动态规划算法：\n');
    printf('%d\n', dynamic());
    printf('分支限界算法：\n');
    printf('%d\n', branch());
    return 0;
}