貪心法的基本思路：從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1. 不能保證求得的最後解是最佳的；
2. 不能用來求最大或最小解問題；
3. 只能求滿足某些約束條件的可行解的範圍。
貪心演算法的運用-背包問題
 
背包問題和0/1背包問題的主要區別就是物品可不可以再分割。背包問題中的物品可以再進行分割，而0/1背包問題中的物品則反之。貪心演算法往往只從局部去考慮問題，所以在解決0/1背包問題時得不到最優解。
 
貪心演算法運用於背包問題的c++實現:

 

物品

A

B

C

D

F

重量

1

2

3

4

5

价值

3

10

6

3

5

程序代码：

  1. //GreedyAlgorithm.h  
  2. #include<iostream>  
  3. using namespace std;  
  4.   
  5. class GreedyAlgorithm{  
  6. public:  
  7.     GreedyAlgorithm(int _weight[],int _value[],int capacity);  
  8.     double *ComputeRatio();  
  9.     void SortRatio(double _Ratio[]);  
  10.     double ComputeProfit();  
  11. private:  
  12.     int *weight;  
  13.     int *value;  
  14.     int capacity;  
  15.     double profit;  
  16. };  
  17. //GreedyAlgorithm.cpp  
  18. #include"GreedyAlgorithm.h"  
  19.   
  20. //================================  
  21. //函数名称：GreedyAlgorithm  
  22. //函数功能：初始化对象  
  23. //函数参数说明:_weight[] 物品重量,_value[] 物品价值,_capacity 背包容量  
  24. //函数返回值：void  
  25. //创建时间：2009-04-28  
  26. //更新：  
  27. //================================  
  28. GreedyAlgorithm::GreedyAlgorithm(int _weight[],int _value[],int _capacity){  
  29.       
  30.     this->weight=_weight;  
  31.     this->value=_value;  
  32.     this->capacity=_capacity;  
  33.     this->profit=0;  
  34.     return;  
  35. }  
  36.   
  37. //================================  
  38. //函数名称：ComputeRatio  
  39. //函数功能：计算出物品的单位价值  
  40. //函数参数说明:  
  41. //函数返回值：double *  
  42. //创建时间：2009-04-28  
  43. //更新：  
  44. //================================  
  45. double *GreedyAlgorithm::ComputeRatio(){  
  46.     double *Ratio=new double[5];  
  47.     for(int i=0;i<5;i++)  
  48.         Ratio[i]=(double)value[i]/weight[i];  
  49.     return Ratio;  
  50. }  
  51.   
  52. //================================  
  53. //函数名称：SortRatio  
  54. //函数功能：根据单位价值比大小，对物品的价值和重量进行排序  
  55. //函数参数说明:  
  56. //函数返回值：void  
  57. //创建时间：2009-04-28  
  58. //更新：  
  59. //================================  
  60. void GreedyAlgorithm::SortRatio(double _Ratio[]){  
  61.     for(int i=0;i<5;i++)  
  62.         for(int j=i+1;j<5;j++)  
  63.         {  
  64.             if(_Ratio[j]>_Ratio[i]){  
  65.                 int temp=weight[i];  
  66.                 weight[i]=weight[j];  
  67.                 weight[j]=temp;  
  68.                 temp=value[i];  
  69.                 value[i]=value[j];  
  70.                 value[j]=temp;  
  71.             }  
  72.         }  
  73.         return;  
  74. }  
  75. //================================  
  76. //函数名称：ComputeProfit  
  77. //函数功能：计算背包的内所放物品的最大价值  
  78. //函数参数说明:  
  79. //函数返回值：double  
  80. //创建时间：2009-04-28  
  81. //更新：  
  82. //================================  
  83. double GreedyAlgorithm::ComputeProfit()  
  84. {  
  85.     int temp=0;  
  86.     int i=0;  
  87.     while(temp<=capacity){  
  88.         if(i==5)    break;  
  89.         else{  
  90.             if((weight[i]+temp)<=capacity){  
  91.                 profit+=value[i];  
  92.                 temp+=weight[i];  
  93.                 }  
  94.             else if((weight[i]+temp)>capacity){  
  95.                 int _weight=capacity-temp;  
  96.                 double _Ratio=(double)value[i]/weight[i];  
  97.                 profit+=_Ratio*_weight;  
  98.                 temp+=_weight;  
  99.             }  
  100.               
  101.         }  
  102.         i++;  
  103.     }  
  104.     return profit;  
  105. }  
  106.   
  107. //main.cpp  
  108. #include<iostream>  
  109. #include"GreedyAlgorithm.h"  
  110. using namespace std;  
  111.   
  112. int main(){  
  113.     int _weight[5]={1,2,3,4,5};  
  114.     int _value[5]={3,10,6,3,5};  
  115.     int _capacity=7;  
  116.     GreedyAlgorithm *greedy=new GreedyAlgorithm(_weight,_value,_capacity);  
  117.     greedy->SortRatio(greedy->ComputeRatio());  
  118.     cout<<"The Maximum Profit is:     "<<greedy->ComputeProfit()<<endl;  
  119.     return 0;  
  120. }  

 

一、动态规划算法介绍

动态规划算法(Dynamic Programming Algorithm, DPA)与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。为了达到此目的，可以用一个表来记录所有已解决的子问题的答案。这就是动态规划法的基本思想。

动态规划算法使用于解最优化问题。通常可按以下4个步骤设计：
1、找出最优解的性质，并刻画其结构特征；
2、递归地定义最优值；
3、以自底向上的方式计算出最优值；
4、根据计算最优值时得到的信息，构造最优解。

步骤1~3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省去。若需要求出问题的最优解，则必须执行步骤4。此时，在步骤3中计算最优值时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速构造出一个最优解。

二、0-1背包问题

【问题描述】：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

【算法分析】：0-1背包问题的最优子结构，设(y1,y2,...,yn)是所给0-1背包问题的一个最优解，则(y2,y3,...,yn)是经过一次选择后的0-1背包问题的最优解。0-1背包问题的递归关系，设当前子问题的最优值为m(i,j)，即m(i,j)使背包容量为j，可选择物品为i,i+1,...,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式：
当i=n时，若j>=wn，则m(i,j)=vn；若0<=j<wn，则m(i,j)=0。
当i<n时，若j>=wi，则m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}；若0<=j<wi，则m(i,j)=m(i+1,j)。

arrow
arrow
    全站熱搜

    戮克 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄