/*
资源分配问题:
是考虑如何把有限的资源分配给
若干个工程问题。假设资源总数为 r，工程个数为
n，给每个工程投入的资源不同，所得的利润也不
同，要求把总数为 r 的资源分配给n个工程，以获
得最大利润的分配方案。
决策过程:
把资源r划分为m个相同的部分，每份资源为r/m，m为整数。假定利润函数为
Gi(x)=把x份资源分配给第i个工程得到的利润
G(m) = i从1到n 累加求和Gi(xi)
i从1到n 累加求和xi = m
牛逼：问题转化为把m份资源分配给n个工程，使得G(m)最大的问题
m份资源
首先，把各个工程按顺序编号，按下述方法进行划分:
第一阶段：分别把x=0,1,...,m份资源给第1份个工程，确定在第一个工程在各种不同份额的资源下，
能够得到最大的利润
第二阶段:分别把x=0,1,...,m份资源分配给第1,2个工程，确定第1个工程在各种不同份额的
资源分配下，这两个工程能够得到的最大利润和第二个工程的最优分配份额。
在第n个阶段，分别把x=0,1,2,...,m份资源分配给所有n个工程，确定能够得到的最大利润，
以及在此利润下，第n个工程的最优分配份额。
考虑到把m份资源全部投入给所有n个工程一定能够得到最大利润，因此必须在各个阶段中，
对不同的分配份额计算，得到最大利润，然后取其中的最大者，作为每个阶段能够取得的
的最大利润。再取每个阶段的最大利润中的最大者，以及在该最大利润下的分配方案，
即为整个资源分配的最优决策
思想:
前缀法
1设fi(x)表示把x份资源分配给前i个工程时，所得到的最大利润，
di(x)表示使得fi(x)最大时，分配给第i个工程的资源份额。
在第一阶段，只把x份资源分配给第一个工程，有:
{f1(x) = G1(x)
{d1(x) = x 0<=x<=m
第二阶段，只把x份资源分配给第一、第二两个工程，有:
{f2(x)=max{G2(z) + f1(x-z)}
{d2(x) = 使得f2(x)最大的z ,0<=x<=m,0<=z<=x
非常重要
第i个阶段，把x份资源分配给前i个工程，有:
Gi(x)=把x分资源分配给第i工程的利润
{fi(x)=max{Gi(z) + fi-1(x-z)}
{di(x) = 使得fi(x)最大的z，0<=x<=m,0<=z<=x
令第i阶段最大利润为gi，则:本质上是遍历各种解决方案
gi = max{fi(1),...,fi(m)}
设qi是使得gi最大时，分配给前面i个工程的资源份额，则:
qi = 使得fi(x)最大的x，这里的qi是整体
di = 使的fi(x)最大的当前工程得到的资源个数
Gi(x) = 把x份资源分配给前i个工程得到的利润
fi(x) = 把x份资源分配给前i个工程得到的最大利润
optg = max{g1,g2,...,gn}
k = 使gi最大的i
optx = 与最大的gi相对应的qi
在每个阶段中，把所得到的所有局部决策值fi(x),di(x),gi,qi保存起来。
最后，在第n阶段结束之后，令全局的最大利润为optg,则：
optg = max{g1,g2,...,gn}
在全局最大利润下，所分配工程项目的最大编号（即所分配工程项目的最大数目）为k，则:
k = 使gi最大的i
分配给前面k个工程的最优份额为:
optx = 与最大的gi相对应的qi[使得fi(x)最大的x]
分配给第k个工程的最优份额为:
optqk = dk(optx)[k是最大的i,optx全局的分配量]
分配给其余k-1个工程的剩余的最优份额为:
optx = optx - dk(optx)
由此回溯，得到分配给前面各个工程的最优份额的递推关系式:
{optqi=di(optx)
{optx=optx-optqi,i = k,k-1,...,1
输入:
3（工程数） 8（资源数），下面3行，每行9列
0 4 26 40 45 50 52 52 53
0 5 15 40 60 70 73 74 75
0 5 15 40 80 90 95 98 100
输出:
140
0 4 4
x 0 1 2 3 4 5 6 7 8
G1(x) 0 4 26 40 45 50 52 52 53
G2(x) 0 5 15 40 60 70 73 74 75
G3(x) 0 5 15 40 80 90 95 98 100
第一步:求各个阶段不同分配的份额时在此利润下的分配额。
第一阶段，只把资源的份额分配给第一个工程:
x 0 1 2 3 4 5 6 7 8
f1(x) 0 4 26 40 45 50 52 52 53
d1(x) 0 1 2 3 4 5 6 7 8
g1 = 53 = max{f1(1),f1(2),...,f1(8)}
q1 = 8
第二阶段，只把资源分配给第1、2个工程
x = 1时，f2(1) = max(G2(0) + f1(1),G2(1) + f1(0)) = max(0 + 4,5 + 0) = 5
x = 2时, f2(2) = max(G2(0) + f1(2),G2(1) + f1(1) ,G2(2) + f1(0))
= max(0 + 26,5 + 4,15+0) = 26
累次计算x=3,4...,8时的f2(x)以及d2(x)的值，有:
x 0 1 2 3 4 5 6 7 8
f2(x) 0 5 26 40 60 70 86 100 110
d2(x) 0 1 0 0 4 5 4 4 5
g2 = 110 = max{f2(1),f2(2),...,f2(8)}
q2 = 使g2取得最大的资源分配总数 = 8
同样计算f3(x)以及d3(x)的值有:
x 0 1 2 3 4 5 6 7 8
f3(x) 0 5 26 40 80 90 106 120 140
d3(x) 0 1 0 0 4 5 4 4 4
g3 = 140
q3 = 8
optg = max{g1,g2,g3} = g3 = 140
optg = 140,optx = 8,k = 3
{optqx = dk(optx)
{optx = optx - optqx
optq3 = d3(optx) =d3(8) = 4,optx = optx - optq3 = 8 - 4 = 4
optq2 = d2(optx) =d2(4) = 4,optx = optx - optq2 = 4- 4 = 0
optq2 = d2(optx) =d1(0) = 0
计算各个工程的最优分配额度
f2(4) = 60
下面求各个阶段的最大利润,以及在此利润下的分配份额
gi=max{fi(1),...,fi(m)}
qi=使得fi(x)最大的x
算法流程:
1计算fi,di。fi(x) = max{Gi(z) + fi-1(x-z)},di(x) = 使fi(x)最大的z，计算方法采取递推方法
2计算gi,qi。gi = max{fi(1),fi(2),...,fi(n)}：对于前i个工程，分配各个资源数下的利润最大值,qi = 使gi最大的x
3计算optg,optq,k。optg = max{g1,g2,...,gn},k=使得全局利润最大的最大工程编号,optq = 使得optx最大的gi对应的qi
4计算optqx。optqx = dk(optx),optx = optx - optqx,直到所有工程计算完毕
*/
/*
关键:
1 令第i阶段最大利润为gi，则:本质上是遍历各种解决方案
gi = max{fi(1),...,fi(m)}
设qi是使得gi最大时，分配给前面i个工程的资源份额，则:
qi = 使得fi(x)最大的x，这里的qi是整体
di = 使的fi(x)最大的当前工程得到的资源个数
Gi(x) = 把x份资源分配给前i个工程得到的利润
fi(x) = 把x份资源分配给前i个工程得到的最大利润
optg = max{g1,g2,...,gn}
k = 使gi最大的i
optx = 与最大的gi相对应的qi
2
1)计算fi,di。fi(x) = max{Gi(z) + fi-1(x-z)},di(x) = 使fi(x)最大的z，计算方法采取递推方法
2)计算gi,qi。gi = max{fi(1),fi(2),...,fi(n)}：对于前i个工程，分配各个资源数下的利润最大值,qi = 使gi最大的x
3)计算optg,optq,k。optg = max{g1,g2,...,gn},k=使得全局利润最大的最大工程编号,optq = 使得optx最大的gi对应的qi
4)计算optqx。optqk = dk(optx),optx = optx - optqi,直到所有工程计算完毕
*/
#include <iostream>
//#include <string>
//#include <fstream>
//#include <vector>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int MAXSIZE = 100;
int g_iMatrix[4][9] =
{
{0,0,0,0,0,0,0,0,0},
{0,4,26,40,45,50,52,52,53},
{0,5,15,40,60,70,73,74,75},
{0,5,15,40,80,90,95,98,100}
};
int g_f[MAXSIZE][MAXSIZE];//g_f[i][x]:表示将x个资源分配给钱前x个工程的最大利润
int g_d[MAXSIZE][MAXSIZE];//g_d[i][x]:表示使得g_f[i][x]最大的z
int g_g[MAXSIZE]; //计算分配给前i个工程的利润最大值，g[i] = max{fi(1),fi(2),...,fi(n)}
int g_q[MAXSIZE]; //g_q[i] = 使得g_g[i]最大的前i个工程的总共资源数
int g_optx; //全局最大利润值
int g_optq; //全局最大利润下的所分配的资源总数
int g_k; //全局最大利润下的最大工程编号
int g_optqArr[MAXSIZE]; //g_optqArr[i]:存储第i个工程分配的资源个数
/*n:表示工程数,m：表示资源数*/
int allocate(int n,int m)
{
//初始时：设置利润最小
memset(g_optqArr,-1,sizeof(g_optqArr));
memset(g_q,-1,sizeof(g_q));
memset(g_g,-1,sizeof(g_g));
memset(g_f,-1,sizeof(g_f));
//动态规划数组赋初始值
for(int j = 0 ; j <= m ; j++)
{
//初始，f1(x) = a[1[j],资源数，等于原来个数
g_f[1][j] = g_iMatrix[1][j];
g_d[1][j] = j;
}
//计算g1
g_g[1] = g_f[1][1];
g_q[1] = 1;
for(int x = 2 ; x <= m ; x++)
{
if(g_g[1] < g_f[1][x])
{
g_g[1] = g_f[1][x];
g_q[1] = x;
}
}
//自底向上求各阶段,外层迭代
for(int i = 2 ; i <= n ; i++)
{
//fi(x) = max(gi(z) + fi-1(x-z)),x属于[0,n],z属于[0,x]
for(int x = 0 ; x <= m ; x++)
{
for(int z = 0 ; z <= x ; z++)
{
int iResult = g_iMatrix[i][z] + g_f[i-1][x-z];
if(g_f[i][x] < iResult)
{
g_f[i][x] = iResult;
//更新当前工程最大利润下的份额
g_d[i][x] = z;
}
}
//更新前i个工程，依次分配1,2,...,n个资源的利润最大值
if(g_g[i] < g_f[i][x])
{
g_g[i] = g_f[i][x];
g_q[i] = x;
}
}
}
//计算全局最大利润
g_optx = g_g[1];
g_optq = g_q[1];//g_q计算错误
g_k = 1;
for(int i = 2 ; i <= n ; i++)
{
if(g_optx < g_g[i])
{
g_optx = g_g[i];
g_optq = g_q[i];
g_k = i;
}
}
//计算资源分配方案,optqi = dk(optx),optx = optx - optqi
for(int i = n ; i >= 1 ; i--)
{
g_optqArr[i] = g_d[i][g_optq];
g_optq -= g_optqArr[i];
}
return g_optx;
}
/*打印结果：全局最大利润，和资源分配方案*/
void printResult(int n)
{
cout << g_optx << endl;
for(int i = 1 ; i <= n ; i++)
{
if(i != 1)
{
cout << " " << g_optqArr[i];
}
else
{
cout << g_optqArr[i];
}
}
cout << endl;
}
void process()
{
int n;
int m;//资源个数
cin >> n >> m;
{
allocate(n,m);
printResult(n);
}
}
int main(int argc,char* argv[])
{
process();
getchar();
system("pause");
return 0;
}
