【題目描述】

總公司擁有高效設(shè)備M臺，準(zhǔn)備分給下屬的N個分公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這M臺設(shè)備才能使國家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原則：每個公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺數(shù)不超過設(shè)備數(shù)M.

【輸入】

第一行有兩個數(shù)，第一個數(shù)是分公司數(shù)N，第二個數(shù)是設(shè)備臺數(shù)M；

接下來是一個N*M的矩陣，表明了第 I個公司分配 J臺機器的盈利。

【輸出】

第一行輸出最大盈利值；

接下N行，每行有2個數(shù)，即分公司編號和該分公司獲得設(shè)備臺數(shù)。

【輸入樣例】

3 3?????????? //3個分公司分3臺機器
30 40 50
20 30 50
20 25 30

【輸出樣例】

70???????????????????????????????????????? //最大盈利值為70
1 1??????????????????????????????????????? //第一分公司分1臺
2 1??????????????????????????????????????? //第二分公司分1臺
3 1??????????????????????????????????????? //第三分公司分1臺

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 30 #define MOD 2520 #define E 1e-12 using namespace std; int a[N][N],f[N][N],res[N][N]; void print(int x,int y) {if(x==0)return;print(x-1,y-res[x][y]);printf("%d %d\n",x,res[x][y]); } int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];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]+a[i][k]){f[i][j]=f[i-1][j-k]+a[i][k];res[i][j]=k;}cout<<f[n][m]<<endl;print(n,m);return 0; }

總結(jié)

以上是生活随笔為你收集整理的机器分配（信息学奥赛一本通-T1266）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。