C++ 机器分配，NOIP，csp
题目描述
【题目描述】
总公司拥有高效设备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
深度优先搜索吧
#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;
}
}
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 20;
int val[maxn][maxn];
int f[maxn][maxn];
void dfs(int mx,int i,int j){
if(i == 0) return;
for(int k = 0;k <= j;k++){
if(f[i-1][k] + val[i][j-k] == mx){
dfs(f[i-1][k],i-1,k);
printf("%d %d\n",i,j-k);
break;
}
}
}
void solve(int n,int m){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
for(int k = 0;k <= j;k++){
if(f[i][j] < f[i-1][j-k] + val[i][k]){
f[i][j] = f[i-1][j-k]+val[i][k];
}
}
}
}
printf("%d\n",f[n][m]);
dfs(f[n][m],n,m);
}
int main(){
int n,m;
//freopen("123.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
scanf("%d",&val[i][j]);
}
}
solve(n,m);
return 0;
}
找到了一个类似你说的search方法，你看看，如果有帮助请点一下采纳，谢谢！
#include<bits/stdc++.h>
using namespace std;
int n,m,a[20][20],pau[20],f[20],ans;//f[i]是答案机器数，pau是当前假设的机器数量
void search(int Nnum,int Nans,int Nm) {//Nnum是现在的公司编号，Nans是现在的盈利，Nm是剩余的机器
if(Nm<0) return;
if(Nnum==n+1) {
if(Nans>ans) {
ans=Nans;
for(int i=1;i<=n;i++) f[i]=pau[i];
}
return;
}
for(int i=0; i<=m; i++)
pau[Nnum]=i,search(Nnum+1,Nans+a[Nnum][i],Nm-i);//i枚举这个公司用多少台机器
return;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);
search(1,0,m);
printf("%d\n",ans);
for(int i=1; i<=n; i++) printf("%d %d\n",i,f[i]);
return 0;
}
背包
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=100000000;
const int N=2e6+10;
const int M=1e3+10;
const int inf=0x7f7f7f7f;
const int maxx=2e5+7;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a*(b/gcd(a,b));
}
template <class T>
void read(T &x)
{
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-')
op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op)
x = -x;
}
template <class T>
void write(T x)
{
if(x < 0)
x = -x, putchar('-');
if(x >= 10)
write(x / 10);
putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
ll res=1%p;
while(b)
{
if(b&1) res=res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
int a[N];
int dp[105][105];
int w[105][105];
int main()
{
SIS;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
for(int k=0;k<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
}
}
cout<<dp[n][m]<<endl;
for(int i=n;i;i--)
{
for(int j=0;j<=m;j++)
{
if(dp[i][m]==dp[i-1][m-j]+w[i][j])
{
a[i]=j;
m-=j;
break;
}
}
}
for(int i=1;i<=n;i++) cout<<i<<' '<<a[i]<<endl;
return 0;
}
Path+区间DP
#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][k]+graph[i][j-k])
{
f[i][j]=f[i-1][k]+graph[i][j-k];
for(int h=1;h<i;h++) path[i][j][h]=path[i-1][k][h];
path[i][j][i]=j-k;//因为改为了“不给”第i家公司k台机器，所以必须如此调整
}
}
cout<<f[n][m]<<endl;
for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
return 0;
}
DFS
#include<bits/stdc++.h>
using namespace std;
int n,m,a[20][20],pau[20],f[20],ans;//f[i]是答案机器数，pau是当前假设的机器数量
void dfs(int Nnum,int Nans,int Nm) {//Nnum是现在的公司编号，Nans是现在的盈利，Nm是剩余的机器
if(Nm<0) return;
if(Nnum==n+1) {
if(Nans>ans) {
ans=Nans;
for(int i=1;i<=n;i++) f[i]=pau[i];
}
return;
}
for(int i=0; i<=m; i++) pau[Nnum]=i,dfs(Nnum+1,Nans+a[Nnum][i],Nm-i);//i枚举这个公司用多少台机器
return;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);
dfs(1,0,m);
printf("%d\n",ans);
for(int i=1; i<=n; i++) printf("%d %d\n",i,f[i]);
return 0;
}
Pascal
var m，n：integer；
i，j，k，max：longint;
f- ，value：array[0..10,0..15] of integer;
procedure show(i，j：longint)； //输出各分公司分配情况
var k：longint;
begin
if i=0 then exit;
for k:=0 to j do
if max=f[i-1,k]+value[i,j-k] then
begin
max:=f[i-1,k];
show(i-1,k);
writeln(i，‘ ‘，j-k);
exit;
end;
end;
begin
readln(n，m);
for I:= 1 to n do
for j:= 1 to m do
read(value[i，j]);
for i:= 1 to n do
for j:=1 to m do
begin
max:=0;
for k：= 0 to j do
if f[i-1,k]+value[i,j-k]>max then
max：=f[i-1,k] + value[i,j-k];
f[i,j]：=max;
end;
writeln(f[n，m]); //输出最大盈利值
show(n，m); //输出分配情况
end.