Resource_allocation.zip_c++ 车间_利润最优_动态规划资源_资源分配 规划_资源规划

/* 1.设计动态规划算法求解资源分配问题，给出算法的非形式描述。 2. 在Windows环境下用C 语言实现该算法。计算10个实例，每个实例中n=30，m=10， Cij为随机产生于范围（0，10^3）内的整数。记录各实例的数据及执行结果（即最优分配方案、 最优分配方案的值）、运行时间。 3. 从理论上分析算法的时间和空间复杂度，并由此解释相应的实验结果。 某厂根据计划安排，拟将n台相同的设备分配给m个车间，各车间获得这种设备后， 可以为国家提供盈利Cij(i台设备提供给j号车间将得到的利润，1≤i≤n，1≤j≤m) 。 问如何分配，才使国家得到最大的盈利？ */ #include<string.h> #include<stdlib.h> #include<time.h> #include<iomanip.h> #include<iostream.h> #include <ctime> #include <stdio.h> #include <windows.h> #define N 31 #define M 11 int a[N][M], b[N][M], c[N][M];//b[i][j]表示用i台设备分配给前j个车间的最大获利，c[i][j]表示获得最优解时第j号车间使用的设备数 void fun(int a[][11],int b[][11],int c[][11])//随机数调试 { int i,j,n,m,k; n = 30; m = 10; for (j = 1; j <= m; ++j)//对于前j车间 for (i = 1; i <= n; ++i)//i个设备 for (k = 0; k <= i; ++k) if (b[i][j] < b[k][j - 1] + a[i - k][j]) { b[i][j] = b[k][j - 1] + a[i - k][j]; c[i][j] = k; } cout<<"最大获利："<<b[n][m]<<endl; cout<<"资源分配方案："<<endl; k = n; for (j = m; j >= 1; j--) { cout<<"第"<<j<<"号车间使用"<<k - c[k][j]<<"台设备。"<<endl; k = c[k][j]; } return ; } void fun(int **a,int **b,int **c,int n,int m)//手动输入调试 { int i,j,k; n--;m--; for (j = 1; j <= m; ++j)//对于前j车间 for (i = 1; i <= n; ++i)//i个设备 for (k = 0; k <= i; ++k) if (b[i][j] < b[k][j - 1] + a[i - k][j]) { b[i][j] = b[k][j - 1] + a[i - k][j]; c[i][j] = k; } cout<<"最大获利："<<b[n][m]<<endl; cout<<"*资源分配方案：**********"<<endl; k = n; for (j = m; j >= 1; j--) { cout<<"*第"<<j<<"号车间使用"<<k - c[k][j]<<"台设备。 *"<<endl; k = c[k][j]; } return ; } int main() { int i, j, n, m, k,ca; char ch; bool flag = true; DWORD start,stop; while(flag==true) { cout<<"************菜单************"<<endl; cout<<"* 1.手动输入 *"<<endl; cout<<"* 2.随机数调试 *"<<endl; cout<<"* 3.退出 *"<<endl; cout<<"*请输入操作序号："; cin>>ch; cout<<"****************************"<<endl<<endl; switch(ch) { case '1': for ( ca = 1; ca <= 10; ca++) { cout<<"*第"<<ca<<"个实例:****************************"<<endl; cout<<"*请输入设备数："; cin>>n; n++; cout<<"*请输入车间数："; cin>>m; m++; int **aa,**bb,**cc;//定义二维动态数组 aa=new int *[n]; bb=new int *[n]; cc=new int *[n]; for( i=0;i<n;i++) { aa[i]=new int [m]; bb[i]=new int [m]; cc[i]=new int [m]; } for( i=0;i<n;i++) { memset(aa[i], 0, m*sizeof(aa[i]));//初始化 memset(bb[i], 0, m*sizeof(bb[i]));//初始化 memset(cc[i], -1, m*sizeof(cc[i]));//初始化 } cout<<"*请输入第i台设备分配给第j个车间的利润："<<endl; for(i = 1; i < n; i++) for(j = 1; j < m; j++) cin>>aa[i][j]; cout<<"******************************************"<<endl; start = GetTickCount(); fun(aa,bb,cc,n,m); stop = GetTickCount(); cout<<"运行时间为："<<stop-start<<endl<<endl; } flag=true;break; case '2': n = 30; m = 10; srand(time(NULL)); for ( ca = 1; ca <= 10; ca++) { cout<<"第"<<ca<<"个实例:"<<endl; memset(a, 0, sizeof(a));//初始化 memset(b, 0, sizeof(b));//初始化 memset(c, -1, sizeof(c));//初始化 for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) a[i][j] = rand() % 1000;//产生随机数(0,10^3) cout<<"第i台设备分配给第j个车间的利润："<<endl; cout<<" "; for (j = 1; j <= m; j++)//输出利润表 cout<<setw(4)<<j; cout<<endl; for (i = 1; i <= n; i++) { cout<<setw(4)<<i; for (j = 1; j <= m; j++) cout<<setw(4)<<a[i][j]; cout<<endl; } start = GetTickCount(); fun(a,b,c); stop = GetTickCount(); cout<<"运行时间为："<<stop-start<<endl<<endl; } flag = true;break; case '3':flag = false;break; } cout<<"***********************************************"<<endl<<endl; } return 0; }