product.cpp

2、 某工厂购进1000 台机器

#include "iostream"
using namespace std;
#include "stdio.h"
inline int Optimize(int num, int n, int m)
{
	int tmpM=n*0.35+(num-n)*0.65; 
	while(tmpM>=m&&tmpM<=num){
		n++;
		tmpM=n*0.35+(num-n)*0.65;
	}
	return n-1;
}
void GreatestBenefits(int * cost, int * path, int ** s, int year, int num, int numNode,int *route)
{
	
	int tmpNode2=numNode-(s[year][1]-s[year][0]+1);  
	//处理第n年效益
	for(int k=s[year][1],kk=0;k>=s[year][0];k--,kk++)
	{
		route[numNode-kk]=k;
		cost[numNode-kk]=k*4500;
	}
	//处理第1年到第n-1年的效益
	//tmpNode1 为第k年 产品数量最小值在 cost数组中的位置
	//tmpNode2 为第k年 产品数量最大值在 cost数组中的位置
	for(int k=year-1;k>=1;k--){
		int benefit;
		int tmpNode1=tmpNode2-(s[k][1]-s[k][0]);
		// i  is the num machine of the k year 
		for(int i=s[k][0],ii=0;i<=s[k][1];i++,ii++){
			int maxNum=i*0.65;
			int minNum=i*0.35;
			int tmp=minNum-s[k+1][0]+1+tmpNode2;  //目前生产到第k＋1年 所剩下数量最少的值，在cost中的位置
			int numtmp=(i*0.65-minNum)/0.3-1;
			numtmp=Optimize(i,numtmp,minNum);
			benefit=numtmp*4500+(i-numtmp)*3500;
			cost[tmpNode1+ii]=cost[tmp]+benefit;
			path[tmpNode1+ii]=tmp;
			route[tmpNode1+ii]=numtmp;
			// the j is the num machine of the k+1 year depend on the k year's machine
			for(int j=minNum+1,jj=1;j<=maxNum;j++,jj++){
				numtmp=(i*0.65-j)/0.3-1;
				numtmp=Optimize(i,numtmp,j);
				benefit=numtmp*4500+(i-numtmp)*3500;
				cost[tmpNode1]=cost[j-s[k+1][0]+1]+benefit;
			//	benefit=((i*0.65-j)/0.3)*4500+(i-(i*0.65-j)/0.3)*3500;
				if((cost[tmp+jj]+benefit)>cost[tmpNode1+ii]){
					cost[tmpNode1+ii]=cost[tmp+jj]+benefit;
					path[tmpNode1+ii]=tmp+jj;
					route[tmpNode1+ii]=numtmp;
				}
			}
		}
		tmpNode2=tmpNode1-1;
	}
		
}
int main()
{
	int year,num;
	cout<<"please input year:"<<endl;
	cin>>year;
	cout<<"please input num:"<<endl;
	cin>>num;
	int **s,*cost,*path,*route;
	s=new int *[year+1];
	for(int i=1;i<=year;i++)
		s[i]=new int[2];

	s[1][0]=s[1][1]=1000;

	for(int i=2;i<=year;i++){
		s[i][0]=0.35*s[i-1][0];
		s[i][1]=0.65*s[i-1][1];
	}
	int numNode=0;
	for(int i=1;i<=year;i++){
		numNode+=s[i][1]-s[i][0]+1;
	}
	
	cost=new int[numNode+2];
	path=new int[numNode+2];
	route=new int[numNode+2];
	GreatestBenefits(cost,path,s,year,num,numNode,route);

	cout<<"the Greatest Benefits is: "<<cost[1]<<endl;
	cout<<route[1]<<" ";
	int tmp=path[1];
	for(int i=1;i<year;i++){
		
		cout<<route[tmp]<<" ";
		tmp=path[tmp];
	}

	return 0;
}