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