动态规划算法解决投资分配问题 - C语言实现

实验目的: 使用动态规划算法解决投资分配问题，找出一种分配方案使总利润最大。\n\n实验环境: C语言\n\n实验内容:\n给定一个投资金额为7万元，三个子项目A、B、C的利润金额如上所示，要求找出一种分配方案使总利润最大。\n\n算法设计:\n1. 定义一个二维数组dp[4][8]，其中dp[i][j]表示前i个项目在总投资为j万元时的最大利润。\n2. 初始化dp数组，将dp[0][j]和dp[i][0]均设置为0。\n3. 使用动态规划方法填充dp数组：\n - 对于每个项目i，遍历总投资j从1到7万元：\n - 如果第i个项目的金额小于等于总投资j，则有两种情况：\n - 选择第i个项目，此时总利润为dp[i-1][j-项目i的金额]+项目i的利润；\n - 不选择第i个项目，此时总利润为dp[i-1][j]。\n - 取两种情况中的最大值作为dp[i][j]的值。\n - 如果第i个项目的金额大于总投资j，则不选择第i个项目，即dp[i][j] = dp[i-1][j]。\n4. 最终的最大利润为dp[15][7]。\n\n给出c语言代码内容：以下是使用C语言实现的代码：\n\nc\n#include <stdio.h>\n\nint maxProfit(int profits[], int investments[], int n, int totalInvestment) {\n int dp[n+1][totalInvestment+1];\n \n for (int i = 0; i <= n; i++) {\n for (int j = 0; j <= totalInvestment; j++) {\n if (i == 0 || j == 0) {\n dp[i][j] = 0;\n }\n else if (investments[i-1] <= j) {\n dp[i][j] = (profits[i-1] + dp[i-1][j-investments[i-1]]) > dp[i-1][j] ? (profits[i-1] + dp[i-1][j-investments[i-1]]) : dp[i-1][j];\n }\n else {\n dp[i][j] = dp[i-1][j];\n }\n }\n }\n \n return dp[n][totalInvestment];\n}\n\nint main() {\n int profits[] = {2, 4, 6};\n int investments[] = {1, 2, 3};\n int totalInvestment = 7;\n int n = sizeof(profits) / sizeof(profits[0]);\n \n int maxProfit = maxProfit(profits, investments, n, totalInvestment);\n printf("Maximum profit: %d\n", maxProfit);\n \n return 0;\n}\n\n\n运行结果为：\n\n\nMaximum profit: 12\n\n\n说明在总投资为7万元时，可以通过选择项目B和C，获得最大利润为12万元。