头歌资源库（23）资源分配

一、问题描述

某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的3个工厂A,B,C，各工厂在获得这种机器后，可以为国家盈利的情况如表1所示。问：这5台机器如何分配给各工厂，才能使国家盈利最大？

表1中第一列S为机器数，A、B、C三列表示3个工厂在拥有不同台数的机器时的盈利值。输出结果为：第一行为三个整数（输出宽度为4，左对齐），分别表示三个工厂得到的机器数量。第二行为一个整数（输出宽度为4，左对齐），表示获得的总利润。

二、算法思想

这个问题可以使用贪心算法来解决。贪心算法是一种简单且高效的算法思想，它每次选择当前最优解，而不考虑全局最优解。下面是解决这个问题的贪心算法的步骤：

根据表1中的数据，计算出每个工厂获得一个机器的盈利能力。将这个值与工厂的编号一起存储。

对工厂的盈利能力进行降序排列，以便优先分配机器给盈利能力较高的工厂。

依次遍历机器，将每台机器分配给盈利能力最高的工厂，直到机器全部分配完毕或者工厂已经获得了5台机器为止。

输出分配方案，即每个工厂分别获得了多少台机器。

这个贪心算法的时间复杂度为O(nlogn)，其中n是工厂的数量。在这个问题中，n=3，因此算法的时间复杂度为常数级别，效率很高。

三、代码实现

#include<stdio.h>int main(void)
{int A[6]={0,3,7,9,12,13};int B[6]={0,5,10,11,11,11};int C[6]={0,4,6,11,12,12};int AB[6][6];int AB_Max[6];int abc[6];int max;int flag;int i,j,k;for(i=0;i<=5;i++){max=0;for(j=0;j<=i;j++){AB[i][j]=A[i-j]+B[j];if(AB[i][j]>max)max=AB[i][j];}AB_Max[i]=max;}max=0;for(j=0;j<=5;j++){abc[j]=AB_Max[5-j]+C[j];if(abc[j]>max){max=abc[j];flag=j;}}max=max-C[flag];int AB_Num=5-flag;for(i=0;i<=AB_Num;i++)//i为分配给B工厂的机器数{if(AB[AB_Num][i]==max){printf("%-4d",AB_Num-i);printf("%-4d",i);break;}}printf("%-4d\n",flag);max=max+C[flag];printf("%-4d\n",max);return 0;
}