游客 注册 | 登录
中文 | En

2589 - 机器分配

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

    总公司拥有高效设备M台， 准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M <= 15，N <= 10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

题目输入

    第1行有两个数，第一个数是分公司数N，第二个数是设备台数M。

    接下来是一个N*M的矩阵，表明了第i个公司分配j台机器的盈利。

题目输出

    第1行输出最大盈利值。

    接下来N行，每行2个数，即分公司编号和该分公司获得设备台数。

输入/输出样例

输入格式

3 3
30 40 50
20 30 50
20 25 30

输出格式

70
1 1
2 1
3 1

C语言解答

#include "stdio.h"
int n,m;
int a[11][16],b[11],f[11][16];
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f[i][j]=f[i-1][j];
			for(k=1;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];
		}
	}
	printf("%d\n",f[n][m]);
	for(i=n;i>=1;i--)
	{
		for(j=m;j>=0;j--)
			if(f[i][m]==f[i-1][m-j]+a[i][j])
			{
				b[i]=j;
				m-=j;
				break;
			}
	}
	for(i=1;i<=n;i++)
		printf("%d %d\n",i,b[i]);
	return 0;
}

C++解答

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

int F[11][16];
int V[11][16];
int Ans=0,N,M;
void init(void);
void Work(void);
int Prim(int,int);

int main()
{	
	init();
	Work();
	
	return 0;
}

void init(void)
{
	memset(F,0,sizeof(F));
	memset(V,0,sizeof(V));
	
	int i,j;
	
	scanf("%d %d",&N,&M);
	
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			scanf("%d",&V[i][j]);
		}
	}
}

void Work(void)
{
	int i,j,k;
	
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			Ans=0;
			
			for(k=0;k<=j;k++)
			{
				if(F[i-1][k]+V[i][j-k]>Ans)
				{
					Ans=F[i-1][k]+V[i][j-k];
				}
			}
			
			F[i][j]=Ans;
		}
	}
	
	printf("%d\n",F[N][M]);
	
	Prim(N,M);
}

int Prim(int x,int y)
{
	int i,j;
	
	if(x==0) return 0;
	
	for(i=0;i<=y;i++)
	{
		if(Ans==F[x-1][i]+V[x][y-i])
		{
			Ans=F[x-1][i];
			Prim(x-1,i);
			printf("%d %d\n",x,y-i);
			break;
		}
	}
}

Java解答

import java.util.*;
public class Main{

	static int n,m;
	static int[] f = new int[20];
	static int[][] w = new int[20][20];
	static int[][] ans = new int[20][20];

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int i,j,k;
		n = sc.nextInt();
		m = sc.nextInt();
	    for (i=1;i<=n;++i)
	    {
	        for (j=1;j<=m;++j)
	        {
	            w[i][j] = sc.nextInt();
	        }
	    }

	    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的值
	                }
	            }
	        }
	    }

	    System.out.print(f[m]);

	    for (i=1,j=m;i<=n;++i)
	    {
	    	System.out.println();
	    	System.out.print(i+" "+ans[i][j]);
	        j-=ans[i][j];   //算出最优方案第i+1~n公司共使用了几台机器，也就是f(i,j)是由f(i+1,?)转移过来的
	    }

	}
	
	
}
请先登陆