程序填空题：求解资源分配问题（动态规划法）

某公司有3个商店A、B、C，拟将新招聘的5名员工分配给这3个商店，各商店得到新员工后，每年的赢利情况如下表所示，求分配给各商店各多少员工才能使公司的赢利最大。



```c++
#include
#include
#define MAXM 10 //最多商店数
#define MAXN 10 //最多投入的人数
using namespace std;
int m,n; //商店数为m,总人数为n
int v[MAXM][MAXN]={0};
int dp[MAXM][MAXN];
int pnum[MAXM][MAXN];

void Plan() //求最优方案dp
{
int maxf,maxj;
for (int j=0;j<=n;j++) //置边界条件
dp[0][j]=0;
for (int i=1;i<=m;i++)
{
for (int s=1;s<=n;s++)
{
maxf=0;
maxj=0;
for (int j=0;@@[j<=s](2);j++)
{
if (@@[(v[i][j]+dp[i-1][s-j])](2)>=maxf)
{
maxf=@@[v[i][j]+dp[i-1][s-j]](2);
maxj=j;
}
}
dp[i][s]=maxf;
pnum[i][s]=maxj;
}
}
}
void dispPlan() //输出最优分配方案
{
int k,r,s;
s=pnum[m][n];
r=n-s; //r为余下的人数
for (k=m;k>=1;k--) //从m到1
{
printf("%d %d\n",k,s);
s=@@[pnum[k-1][r]](2); //求下一个阶段分配的人数
r=r-s; //余下人数递减
}
printf("%d",dp[m][n]);
}
int main()
{
int i,j;
cin>>m>>n;
for(i=0;i<=m;i++)
for(j=0;j<=n;j++)
cin>>v[i][j];
Plan();
dispPlan();
return 0;
}
```
### 输入格式:

第一行输入商店数m及员工人数n，再依次输入m+1行，每行为n+1个数，每个数（i,j）表示i商店分配j人赢利值0≤i≤m,0≤j≤n。

### 输出格式:

输出前m行每行两个数，分别表示商店编号及分配人数，最后一行表示公司最大赢利。

### 输入样例1:

```in
3 5
0 0 0 0 0 0
0 3 7 9 12 13
0 5 10 11 11 11
0 4 6 11 12 12
```

### 输出样例1:

```out
3 3
2 2
1 0
21
```








答案：
第1空：j<=s

第2空：(v[i][j]+dp[i-1][s-j])

第3空：v[i][j]+dp[i-1][s-j]

第4空：pnum[k-1][r]