题目描述
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入输出格式
输入格式：
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。
接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。
输出格式：
第1行为最大盈利值
第2到第n为第i分公司分x台
P.S.要求答案的字典序最小
输入输出样例
输出样例#1：
70 1 1 2 1 3 1
分析：dp（i，j)表示前I个公司一共选J台机器的最优答案，那转移方程为dp(i,j)=max(dp(i-1,j-k);这个方程表示如果我们第I选择了J台，那应该是从i-1次中选择K台才得出的答案；
那么如何输出字典序最小呢？我们可以使用pa(i,j,h) 表示前i个公司一共选j台机器，h号公司选了多少台；
#include<bits/stdc++.h>
using namespace std;
int f[11][16],graph[11][16],path[11][16][11],n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>graph[i][j];
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++)
{
if (f[i][j]<f[i-1][j-k]+graph[i][k])
{
f[i][j]=f[i-1][j-k]+graph[i][k];
for(int h=1;h<i;h++) path[i][j][h]=path[i-1][j-k][h];//path数组只有在状态发生转移时才更新
path[i][j][i]=k;
}
}
cout<<f[n][m]<<endl;
for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
return 0;
}
但是！！！！！！！这并不可以AC 因为还有个限制条件那就是字典序最小，我们怎么解决呢？？
按上面这种方式的枚举，我们都是尽可能的选满填充所以得出的字典序可能是最大的，那我们可以尽可能的不选满，那就是意味着我们要倒叙的枚举
#include<stdio.h>
#include<string.h>
int mo[20][20],dp[20][20],pa[20][20][20];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1 ; i<=n ; i++)
for(int j=1 ; j<=m ; j++)
scanf("%d",&mo[i][j]);
memset(dp,0,sizeof(dp));
for(int i=1 ; i<=n ; i++)
{
for(int j=0 ; j<=m ; j++)
{
for(int k=0 ; k<=j ; k++)
{
if(dp[i][j]<dp[i-1][k]+mo[i][j-k])
{
dp[i][j]=dp[i-1][k]+mo[i][j-k];
for(int h=1 ; h<i ; h++)
pa[i][j][h]=pa[i-1][k][h];
pa[i][j][i]=j-k;
}
}
}
}
printf("%d
",dp[n][m]);
for(int i=1 ; i<=n ; i++)
printf("%d %d
",i,pa[n][m][i]);
return 0 ;
}
这里给的数据很小，如果数据大的话，有个空间优化
#include <iostream>
using namespace std;
int f[20],n,m,w[20][20],ans[20][20];
int main()
{
int i,j,k;
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>w[i][j];
}
}
for (i=n;i>0;--i)
{
for (j=m;j>=0;--j)
{
for (k=1;k<=j;++k)
{
if (f[j-k]+w[i][k]>f[j])
{
f[j]=f[j-k]+w[i][k];
ans[i][j]=k; //保存f(i,j)取最大时k的值
}
}
}
}
cout<<f[m];
for (i=1,j=m;i<=n;++i)
{
cout<<endl<<i<<" "<<ans[i][j];
j-=ans[i][j]; //算出最优方案第i+1~n公司共使用了几台机器，也就是f(i,j)是由f(i+1,?)转移过来的
}
return 0;
}