问题：
现有设备n台，可投放到m个项目中，每个项目的产量与投入该项目的设备数量有关。如表2所示为三个项目的产量（吨）和投入设备（台）的关系。求对m个项目的最优设备分配，使总产量效益最大。
表2 项目产出与投入的设备数量之间的关系
| 项目产出 投入设备数量 | 项目1（吨） | 项目2（吨） | 项目3（吨） |
| 1台 | 10 | 25 | 11 |
| 2台 | 36 | 29 | 30 |
| 3台 | 40 | 43 | 45 |
| 4台 | 59 | 55 | 58 |
输入描述：
输入第一行包含两个整数n,m，用空格隔开，分别表示设备的数量和项目的数量。其后有n行，每行有m个整数,分别表示1,…,n台设备分别投入到m个项目之后的产量产出。每个整数之间用空格隔开。
输出描述：
输出一个整数,表示将n台设备全部投入到m个项目中所能得到的最大产量。
样例输入：
4 3
10 25 11
36 29 30
40 43 45
59 55 58
输出：
72
思路：
回溯法
代码：
#include<bits/stdc++.h>
using namespace std;int n, m;int dfs(int** relation, int* has, int cnt, int total)
{int result = 0;if(cnt > n) return total;for(int i = 1; i <= m; i++){has[i] = has[i] + 1;int new_total = total+relation[has[i]][i]-relation[has[i]-1][i];int this_time = dfs(relation, has, cnt+1, new_total);has[i] = has[i] - 1;if(this_time > result) result = this_time;}return result;
}
void Delete(int** relation, int* has)
{for(int i = 0; i <= n+1; i++){delete [] relation[i];}delete [] relation;delete [] has;
}
int main()
{cin >> n >> m;int **relation = new int*[n+2];int *has = new int[n+2]();for(int i = 0; i <= n+1; i++){relation[i] = new int[m+2]();}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> relation[i][j];}}int result = 0;result = dfs(relation, has, 1, 0);cout << result << endl;Delete(relation, has);return 0;
}
