动态规划算法解决机器分配问题：最大化盈利

{/'title/':/'动态规划算法解决机器分配问题：最大化盈利/',/'description/':/'本文介绍使用动态规划算法解决经典的机器分配问题，旨在最大化国家盈利。通过清晰的代码示例和详细解释，帮助您理解动态规划的原理，并学会如何将其应用于实际问题。/',/'keywords/':/'动态规划, 机器分配, 算法, 优化, 盈利最大化, C++代码/',/'content/':/'///'动态规划///' 机器分配//n时间限制5000MS//n内存限制64MB//n描述//n//n总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。//n//n//n输入//n输入数据文件格式为：第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。//n//n接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。//n//n//n输出//n输出第一行为最大盈利值；//n//n//n输入样例 1 //n//n3 3 //n30 40 50//n20 30 50//n20 25 30//n输出样例 1//n//n70//nc++代码内容：cpp//n#include <iostream>//n#include <vector>//n#include <algorithm>//nusing namespace std;//n//nint main() {//n int N, M;//n cin >> N >> M;//n vector<vector<int>> profits(N, vector<int>(M));//n for (int i = 0; i < N; i++) {//n for (int j = 0; j < M; j++) {//n cin >> profits[i][j];//n }//n }//n//n // dp[i][j] represents the maximum profit with j machines for the first i companies//n vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));//n for (int i = 1; i <= N; i++) {//n for (int j = 0; j <= M; j++) {//n for (int k = 0; k <= j; k++) {//n dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + profits[i - 1][k]);//n }//n }//n }//n//n cout << dp[N][M] << endl;//n//n return 0;//n}//n/