用贪心的算法更改下面代码 #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int INF = 1e9; int profit[4][7] = { {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 dp[10][10][10]; int main() { memset(dp, 0, sizeof(dp)); for (int i = 0; i < 7; i++) for (int j = 0; j < 7; j++) for (int k = 0; k < 7; k++) { dp[i][j][k] = max(dp[i][j][k], profit[1][i] + profit[2][j] + profit[3][k]); } int n = 0; cin >> n; int l = -1, r = -1, m = -1, res = -1; for (int i = 0; i < 7; i++) for (int j = 0; j < 7; j++) for (int k = 0; k < 7; k++) if (i + j + k == n && res < dp[i][j][k]) { res = dp[i][j][k]; l = i; r = j; m = k; } printf("%d %d %d\n", l, r, m); cout << "你好" << endl; printf("%d", res); return 0; }

这段代码是一个三维的背包问题，用动态规划的思想解决，时间复杂度为 $O(n^3)$。如果要用贪心算法改进，可以考虑将三维背包问题转化为一维背包问题，具体操作如下：

1. 将三种物品合并成一种物品，即将 $profit[1][i] + profit[2][j] + profit[3][k]$ 合并为 $profit[i+j+k]$。

2. 将一维数组 $dp$ 初始化为 $-INF$。

3. 对于每个物品 $i$，从 $n$ 到 $i$ 枚举背包容量 $j$，更新 $dp[j]$：

$dp[j] = max(dp[j], dp[j-i]+profit[i])$

4. 最终 $dp[n]$ 即为最优解。

改进后的代码如下：

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

const int INF = 1e9;
int profit[22] = {0, 3, 5, 6, 7, 6, 5, 4, 6, 7, 8, 9, 10, 2, 5, 9, 8, 8, 7};
int dp[100];

int main() {
    memset(dp, -INF, sizeof(dp));
    dp[0] = 0;
    int n = 0;
    cin >> n;
    for (int i = 1; i <= 18; i++) {
        for (int j = n; j >= i; j--) {
            dp[j] = max(dp[j], dp[j-i]+profit[i]);
        }
    }
    cout << "你好" << endl;
    printf("%d", dp[n]);
    return 0;
}