10-3.cpp

数据结构——动态规划算法

#include <iostream.h>
int c[10],u[10];
float r[10];
struct Node{
	Node *child,*brother,*brother1,*father;
	float f;
	int x,g;
};

bool compare(Node *child,Node *root){
	//根据优化原理,如果f1>f2且x1<x2,那么(f2,x2)是不会产生最优解的
	//(f1,x1)优于(f2,x2),(f2,x2)可淘汰掉
	root=root->child;
	if(root){
		if(child->f<root->f&&child->x>root->x) return false;
		if(child->f>root->f&&child->x<root->x)
			root->brother1->brother=root->brother;
		while(root->brother){
			root=root->brother;
			if(child->f<root->f&&child->x>root->x) return false;
			if(child->f>root->f&&child->x<root->x)
				root->brother1->brother=root->brother;
		}
	}
	return true;
}

void dynamic(int n,int C,Node *root){
	//求出S(1)到S(n)中可能达到最优解的局部解
	for(int i=0;i<n;i++){
		int j=1;
		Node *ROOT=root,*p=root;
		while(root){
			while(j<=u[i]){
				Node *child=new Node;
				float ff=1;
				for(int k=1;k<=j;k++) ff*=(1-r[i]);
				child->f=root->f*(1-ff);
				child->x=root->x+j*c[i];
				child->g=j;
				child->brother=NULL;
				child->child=NULL;
				child->father=root;
				int ccc=0;
				for(int q=i+1;q<n;q++) ccc+=c[q];
				if(child->x<=(C-ccc)){
					if(compare(child,ROOT)==1){
						p=root->child;
						if(!p){
							root->child=child;
							if(root->brother1){
								if(root->brother1->child){ 
									Node *r=root->brother1->child;
									while(r->brother) r=r->brother;
									child->brother1=r;
									r->brother=child;
								}
							}
							else child->brother1=NULL;
						}
						else{
							while(p->brother) p=p->brother;
							child->brother1=p;
							child->brother1->brother=child;
						}
					}
				}
				j++;
			}
			root=root->brother;
			j=1;
		}
		root=ROOT->child;
	}
}

Node *show(int n,Node *root){
	//从S(n)中得到最优设计方案
	Node *p=root;
	for(int i=0;i<n;i++) p=p->child;
	int MAX=p->x;
	Node *t=p;
	while(p->brother){
		p=p->brother;
		if(MAX<p->x){
			MAX=p->x;
			t=p;
		}
	}
	return t;
}
		

void main(){
	cout<<"n = ";
	int n;
	cin>>n;
	int CC=0;
	for(int i=1;i<=n;i++){
		cout<<"c"<<i<<" = ";
		cin>>c[i-1];
		CC+=c[i-1];
	}
	cout<<"C = ";
	int C;
	cin>>C;
	for(i=1;i<=n;i++){
		cout<<"r"<<i<<" = ";
		cin>>r[i-1];
	}
	for(i=0;i<n;i++) u[i]=(C+c[i]-CC)/c[i];
				//u表示可并联的各级部件的最大值
	Node *root=new Node;
	root->f=1;
	root->x=root->g=0;
	root->brother=root->brother1=root->child=NULL;
	dynamic(n,C,root);
	cout<<endl;
	Node *t=show(n,root);
	cout<<"f = "<<t->f<<endl<<"x = "<<t->x<<endl;
	for(i=n;i>0;i--){
		cout<<"m"<<i<<" = "<<t->g<<endl;
		t=t->father;
	}
}	

//程序使用的算法思想是：动态规划算法
//这一问题是如何通过配置多重部件来组成一个系统，在一定条件下使可靠性
//最大，这一定的条件就是这个系统的成本。
//若用S(i)记录有可能达到最优解的局部解，再依次计算S(i+1)中有可能达到
//最优解的有序对，直到在S(n)中找到最优方案，再返回来从S(n-1),S(n-2),
//…,S(1)中依次确定m值
//本程序采用孩子兄弟表示法来作为树的存储结构