Liny_@NotePad

沉迷ACG中

动态规划求解资源最优分配问题

YOYO posted @ 2009年4月29日 08:12 in 【算法】与【数据结构】 with tags 动态规划 , 4759 阅读

为第i个工程计算最优时，只需将分配若干给前i-1个工程、剩下的留给当前工程得到的各种分配方案，和只分配给当前工程的方案，取其中的最大值即可；而第一个工程解就是只分配给自身的解。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define M 10    //  最多资源份量
  5. #define N 10    //  最多工程数量
  6.  
  7. int g[M+1][N];  //        资源分配利润函数
  8. int solve[N];      // 最优分配方案
  9. int m, n;              //     资源数与工程数
  10.  
  11. int dp(){
  12.         int f[M+1][N];  //        资源分配最多利润
  13.         int d[M+1][N];  //        资源分配方案
  14.         int best;                     //     资源分配最优方案可得利润best，
  15.         int bi, bj;          //   最优时资源分配给了前bi个项目，共分配bj份资源
  16.         int i,j,k;
  17.  
  18.         //      先得到只有第一个工程时的利润
  19.         for(i=0; i<=m; i++){
  20.                 f[0][i] = g[0][i];
  21.                 d[0][i] = i;
  22.         }
  23.  
  24.         //      计算n个工程的资源分配表
  25.         for(i=1; i<n; i++){
  26.                 f[i][0] = g[i][0] + f[i-1][0], d[i][0] = 0;     //   当为0时解直接相加
  27.                 for(j=1; j<=m; j++){
  28.                         f[i][j] = f[i][0], d[i][j] = 0; //       初始化为不分配给该工程资源时的解
  29.                         for(k=0; k<=j; k++){        //  计算分配给其若干个资源时的最优解
  30.                                 if(f[i-1][j-k] + g[i][k] > f[i][j]){
  31.                                         f[i][j] = f[i-1][j-k] + g[i][k];
  32.                                         d[i][j] = k;
  33.                                 }
  34.                         }
  35.                 }
  36.         }
  37.  
  38.         //      寻找最优分配方案
  39.         for(i=0; i<n; i++){
  40.                 for(j=0; j<=m; j++){
  41.                         if(f[i][j]>best){
  42.                                 best = f[i][j];
  43.                                 bi = i, bj = j;
  44.                         }
  45.                 }
  46.         }
  47.  
  48.         //      计算每个工程各消耗多少资源
  49.         memset(solve, 0, sizeof(solve));
  50.         k = bj;
  51.         for(i=bi; i>=0; i--){   // bi以后的项目都不用分配
  52.                 solve[i] = d[i][k];
  53.                 k-=solve[i];
  54.         }
  55.  
  56.         return best;
  57. }
  58.  
  59. int main(){
  60.         int i,j;
  61.  
  62.         cin>>m>>n;
  63.        
  64.         for(i=0; i<n; i++){
  65.                 for(j=0; j<=m; j++){
  66.                         cin>>g[i][j];
  67.                 }
  68.         }
  69.  
  70.         cout<<"最优分配方案可得利润："<<dp()<<endl;
  71.  
  72.         cout<<"最优分配方案："<<endl;
  73.         for(i=0; i<n; i++){
  74.                 cout<<"工程"<<(i+1)<<"分配："<<solve[i]<<"资源"<<endl;
  75.         }
  76.  
  77.         return 0;
  78. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter