贪心算法求解问题(优化版).docx

贪心算法求解问题问题分析：此问题为程序最优存储问题，问题要求最后存储的两个磁带上的长度差异就最小。若在最优解中去掉i个程序段，显然在（n-i）个程序段的存储中应仍是最优解，因为此问题存在最优子结构。另外，由于每个程序的长度不同，每将一个程序存储到A或者B（用A和B来表示两个磁带上存储程序的集合）后，显然还与后续怎么存储程序有关，即当前结果依赖子问题的结果。这正是动态规划算法的基本特征，而贪心算法仅在当前状态下做出最好选择，然后再去做子问题的局部最优解最终就是问题的最优解，贪心算法不依赖于将来所做的子问题的解，显示，此问题是一个动态规划问题，是一个0-1背包问题。虽然对有些问题，贪心算法并不能得到一个最优解，但往往能快速地得到一个近似最优解。下面就来讨论如何用贪心算法得到近似最优解。 贪心算法思路为了使最后两个磁带的长度差异越小，就先将长度较大的程序优先放入到磁带（此处用A和B分别表示两个磁带）上。因此排序选择递减排序。用p 数组来存放第i个程序长度为pi-1，首先将其按程序长度大小递减的顺序排序，将排好序的各程序下标记录到与与p等长的数组a 中。然后再根据a中记录的下标找到相应的程序pai放到A或者B中。现在就接下就是如何存放来达到近似最优解的问题了开始A和B中没有任何元素（本程序中采用vector动态定义A，B），如果用sumA和sumB来标记A和B中已存入程序的总长度，在存入当前最优解时，先比较sumA和sumB 的大小，将最优解存入到程序总长度较短的那个程序集合，如果长度一样，则存入到A或者B中（本程序是存入到A集合中），可以看到这样存入的话，就会尽量减小A和B长度的差异，从而尽量接近最优存储得到近似最优解之前提交的贪心算法的思想是直接交叉存入到A和B中，那样得到的解在一定程度能得利近似最优解，那种思想只对程序段长度相差小的情况有比较好的结果，因为那种思想大概是将程序段平均到A和B中，在很多情况下不能得到近似最优解。这些优化最重要是核心思想上的优化，这次程序设计中，在放入A或者B前先比较A和B的长度，这样才更有针对性的存放，得到的效果比之前的好了很多，另外在，程序实现代码上也有了很大的优化，代码优化见“代码优化说明”程序源代码（Microsoft Visual Studio 2010）/ 贪心算法求解问题.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#includeusing namespace std;/将各程序按长度的递减顺序排序，用a 来记录排好序程序的下标void Rank(vectorp,vector&a,int n)int t;for(int j =0;jn-1;j+)for(int i=0;in-1-j;i+)if(pipi+1) t=pi;pi=pi+1;pi+1=t;t=ai;ai=ai+1;ai+1=t;/采用贪心算法将程序长度最大的放入到A和B中void GreedySelector(vector&p,vector&A,vector&B,vector&a,int n)int sumA=0; /定义A中程序的总长度int sumB=0; /定义B中程序的总长度int m=0,j=0; /用m标志A数组的长度，n标志B数组的长度/将当前的最优解（最大长度）存入到A、B中总长度较短一个集合for(int i=0;i=sumA) A.resize(+m); /当有数据存入时，动态将A数组长度加1Am-1=ai; sumA+=pAm-1; /计算A中程度总长度else B.resize(+j);Bj-1=ai;sumB+=pBj-1;int _tmain(int argc, _TCHAR* argv)int n;coutn;vectorA,B; /定义动态数组A和B并初始化他要0vectorp(n),a(n); /p(n)用来存放第(n-1)个程序的长度，a(n)存放排好序的元素下标for(int i=0;in;i+)cout请输入第i+1pi;a0=0;for(int i=1;in;i+) /用a 数组初始化各程序排序的下标ai=ai-1+1;Rank(p,a,n); /调用排序函数GreedySelector(p,A,B,a,n); /调用贪心算法将程序放入到A和B中int sum1=0,sum2=0;for(int i=0;iA.size();i+) /计算存放在A中程序总长度sum1+=pAi;for(int i=0;iB.size();i+) /计算存放在B中程序总长度sum2+=pBi;coutendl;cout-贪心算法结果-endl;cout用贪心算法近似最优值为： sum1和 sum2endl;cout用贪心算法近似最优解如下 :endl;cout一磁带上的程序组合为：endl;for(int i=0;iA.size();i+) /输出A中的程序集合coutpAi+1 ;coutendl;cout另一磁带上的程序组合为：endl;for(int i=0;iB.size();i+) /输出B中的程序集合coutpBi+1 ;coutendl;return 0;实验结果运行实例一运行实例二运行实例三从上面的结果可以看到，用优化的的贪心算法基本上都能得到最优解代码优化说明1 为了一定的动态灵活性，程序要求由用户输入程序的个数n以及每个程序的长度pi，并用vector动态定义相关数组。2 此处为了节省内存空间，将每个数组下标为0的变量也利用起来，避免了对内存空间的浪费。3 在定义A和B时，A和B的长度初始时为0，但需要存入一个一个数据时，通过A.resize(+m)和B.resize(+j)来动态为A和B数据增加长度并写入相应的数据。这样大大节省了程序对内存的开销。算法设计不足之处：由于此问题本来不太适用于贪心算法，本程序只是在贪心算法中尽量选择一个比较好的贪心算法，让结果尽量近似最优值。可以看到，如果在这些程序中，存在一个最优解的情况是程序中最大长度的两个程序为一组