C++ 机器分配，NOIP，csp

Question

题目描述
【题目描述】
总公司拥有高效设备MM台，准备分给下属的NN个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这MM台设备才能使国家得到的盈利最大？求出最大盈利值。其中M\le 200M≤200，N\le 100N≤100。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数MM。
输入格式
第一行有两个数，第一个数是分公司数NN，第二个数是设备台数MM。
接下来是一个N\times MN×M的矩阵，第ii行第jj列表明了第ii个公司分配jj台机器的盈利。 不超过10^410
4
。
输出格式
第1行为最大盈利值
第2到第n+1n+1行, 每行两个整数，为ii和第ii个公司分到的台数
要求答案的字典序最小

输入样例
输入
3 3
30 40 50
20 30 50
20 25 30
输出样例
输出
70
1 1
2 1
3 1

Answer 1

深度优先搜索吧

#include <bits/stdc++.h>
using namespace std;
int n,m,a[11][20],b[20],jians[20],ans;
void dfs(int zhi,int b[],int qian,int k)
{
 
        if(qian>ans)
        {
            ans=qian;
            for(int i=1;i<=n;i++)
            {
                jians[i]=b[i];
            }
        }
    if(zhi==0)
    return;
    if(k==0)
    return;
    for(int i=m;i>=0;i--)
    {
        if(zhi>=i)
        {
            b[k]=i;
            dfs(zhi-i,b,qian+a[k][i],k-1);
            b[k]=0;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    dfs(m,b,0,n);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        cout<<i<<" "<<jians[i]<<endl;
    }
}