“插花问题”的动态规划法算法

ysslctds

//:============================“插花问题”的动态规划法算法============================#define F 100#define V 100/**//*    插花问题描述:            将f束鲜花插入v个花瓶中,使达到最徍的视觉效果,        问题相关约定及插花要求:            鲜花被编号为1--f,花瓶被编号为1--v,花瓶按从小到        大顺序排列,一只花瓶只能插一支花,鲜花i插入花瓶j中的        视觉效果效果值已知,编号小的鲜花所放入的花瓶编号也小        问题求解思路:            花瓶j(1        小的鲜花所放入的花瓶编号也小);            设数组p[j]表示鲜花i插入花瓶j的好看程度,数组        q[j]表示[1..i]束鲜花插入[1..j]个花瓶所能得到的最大        好看程度,初始化q[0][0] = 0;q[0][j]=0(1        是问题的解.            特别地,j束鲜花插入到前面的j只花瓶中,所得到的好看        程度是q[j][j] = p[1][1]+p[2][2]+...+[j][j].现将插花过        程按花瓶排列顺序划分成不同阶段,则在第j阶段,第i束鲜花        若放入第j号花瓶,最大好看程度是q[i-1][j-1]+p[j];第i束鲜        花若放入前j-1个花瓶中的某一个,所得的好看程度是q[j-1],        那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:        q[j] = MAX(q[i-1][j-1]+p[j],q[j-1]),要使q[j]        最大,应使q[i-1][j-1]和q[j-1]也最大*/#define MAX(A,B) ((A) > (B) ? (A)B))        //求取两数的最大值宏定义#define F 100                    //鲜花数最大值常量定义#define V 100                    //花瓶数最大值常量定义//“插花问题”的初始化函数//    int    f,v:        鲜花数量，花瓶个数//    int    p[][v]:        鲜花i插入花瓶j的好看程度void Flower_Initialize(int *f,int *v,int p[][V])...{    int i,j;    printf("输入鲜花数量及花瓶个数:");    scanf("%d%d",f,v);    printf("顺序输入各鲜花插入各花瓶的好看程度: ");    for(i=1;i        for(j=1;j            p[j] = i*j;            //scanf("%d",;p[j]);}//“插花问题”的动态规划法解决函数//    int    p[][v]:        鲜花i插入花瓶j的好看程度//    int    f,v:        鲜花数量，花瓶个数//    int    *way:        鲜花插入花瓶的插入方法结果int        Ikebana(int p[][V],int f,int v,int *way)...{    int    i,j,q[F][V],newv;    q[0][0] = 0;    //初始化[没有一束花插入花瓶时],好看程度自然为0    //设置v个花瓶分别被插入v束鲜花时各号花瓶对应的(初始)最大好看程度    for(j = 1;j     ...{        q[0][j] = 0;        //设置第j束鲜花放入第j号花瓶中的最大好看程度        q[j][j] = q[j - 1][j - 1] + p[j][j];    }    for(j = 1;j         for(i = 1;i             q[j] = MAX(q[i - 1][j - 1] + p[j],q[j - 1]);    newv = v;    for(i = f;i > 0;i--)    ...{        while(q[i-1][newv-1]+p[newv]             newv--;        //确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶        way = newv--;    }    return(q[f][v]);}//测试“插花问题”的动态规划法函数void    Run_Ikebana()...{    //循环计数器，鲜花数量，花瓶个数，鲜花i插入花瓶j的好看程度，鲜花插入花瓶的插入方法结果    int    i,f,v,p[F][V],way[F];    Flower_Initialize(;f,;v,p);    printf("最大好看程度点数为%d ",Ikebana(p,f,v,way));    printf("插有鲜花的花瓶是: ");    for(i = 1;i         printf("%4d",way);}//:============================“插花问题”的动态规划法算法============================int main(int argc, char* argv[])...{    //Run_SubString();    Run_Ikebana();    printf(" 应用程序运行结束！ ");    return 0;}