贪心算法 背包问题.doc

贪心算法 背包问题.txt精神失常的疯子不可怕，可怕的是精神正常的疯子！#include#includeusing namespace std;struct good/表示物品的结构体 double p;/价值 double w;/重量 double r;/价值与重量的比a2000;double s,value,m;int i,n;bool bigger(good a,good b) return a.rb.r;int main() scanf(%d,&n);/物品个数 for (i=0;in;i+) scanf(%lf%lf,&ai.w,&ai.p); ai.r=ai.p/ai.w; sort(a,a+n,bigger);/调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心 scanf(%lf,&m);/读入包的容量m s=0;/包内现存货品的重量 value=0;/包内现存货品总价值 for (i=0;in&s+ai.w=m;i+) value+=ai.p; s+=ai.w; printf(The total value in the bag is %.2lf.n,value);/输出结果 return 0; 贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。 选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。 假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（1=i=n,0=xi=1)装入背包中，则有价值pi*xi。在约束条件（w1*x1+w2*x2+wn*xn)=M下使目标(p1*x1+p2*x2+pn*xn)达到极大，此处0=xi0,1=i=n.这个问题称为背包问题（Knapsack problem）。 要想得到最优解，就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说，总应该把那些单位效益最高的物体先放入背包。 在实现算法的程序中，实现算法的核心程序倒没碰到很大的问题，然而实现寻找最优度量标准程序时麻烦不断！ 在寻找最优度量标准时，大致方向是用冒泡排序算法。也就是根据pi/wi的大小来对wi来排序。 在直接用此算法时，可以有如下的一段代码： /根据效益tempArrayi对重量wi排序，为进入贪心算法作准备 1 void sort(float tempArray, flaot w, int n) 2 3 int i = 0, j = 0; 4 int index = 0; 5 6 /用类似冒泡排序算法，根据效益pi/wi对wi排序 7 for (i = 0; i n; i+) 8 9 float swapMemory = 0; 10 float temp; 11 12 temp = tempArrayi; 13 index = i; 14 15 for (j = i + 1; j n; j+) 16 17 if (temp tempArrayj) 18 19 temp = tempArrayj; 20 index = j; 21 22 23 24 /对wi排序 25 swapMemory = windex; 26 windex = wi; 27 wi = swapMemory; 28 29 30 return; 31 然而仔细对算法分析后可以发现，“拿来主义”在这里用不上了！ 对算法的测试用例是p3 = 25, 24, 15;w3 = 18, 15, 10。得到的结果如下： please input the total count of object: 3 Please input array of p : 25 24 15 Now please input array of w : 18 15 10 sortResulti is : 1 -107374176.000000 1 1.600000 2 1.600000 after arithmetic data: xi 0.000000 0.333333 0.000000 可以看到其效益为x3 = 1.4, 1.6, 1.5，于是在M = 20的情况下，其预想中的输出结果是0，1，0.5。然而事实上是不是就这样呢？ 当程序进入此函数经过必要的变量初始化后，进入了外围循环，也就是程序的第7行。第一轮循环中，temp = tempArray0 = 1.4,index = i = 0;程序运行到第15行，也就是进入了内层循环。 内层循环的主要任务是从第i + 1个元素之后找到一个最大的效益并保存此时的下标。到了第24行后，就开始对wi进行排序。 问题就在这里了！排序后的wi = 1.6, 1.6, 1.5，因此对wi排序后就既改变了wi的原有顺序，还改变了wi的原来值！ 据此，做出一些修改，得到了如下的一段代码： 1 void sort(float tempArray, int sortResult, int n) 2 3 int i = 0, j = 0; 4 int index = 0, k = 0; 5 6 for (i = 0; i n; i+)/对映射数组赋初值0 7 8 sortResulti = 0; 9 10 11 for (i = 0; i n; i+) 12 13 float swapMemory = 0; 14 float temp; 15 16 temp = tempArrayi; 17 index = i; 18 19 for (j = i; j n; j+) 20 21 if (temp tempArrayj) & (sortResultj = 0) 22 23 temp = tempArrayj; 24 index = j; 25 26 27 28 if (sortResultindex = 0) 29 30 sortResultindex = +k; 31 32 33 34 for (i = 0; i n; i+) 35 36 if (sortResulti = 0) 37 38 sortResulti = +k; 39 40 41 42 return; 43 修改后最大的一个改变是没有继续沿用直接对wi排序，而是用wi的一个映射数组sortResulti。sortResulti中元素值存放的是根据效益计算得wi的大小顺序！这样wi原有的值和位置都没有改变，从而使算法得以实现！ 至于有没有更好的实现版本，还在探索中！ #include #define MAXSIZE 100 /假设物体总数 #define M 20 /背包的载荷能力 /算法核心，贪心算法 void GREEDY(float w, float x, int sortResult, int n) float cu = M; int i = 0; int temp = 0; for (i = 0; i n; i+)/准备输出结果 xi = 0; for (i = 0; i cu) break; xtemp = 1;/若合适则取出 cu -= wtemp;/将容量相应的改变 if (i = n)/使背包充满 xtemp = cu / wtemp; return; void sort(float tempArray, int sortResult, int n) int i = 0, j = 0; int index = 0, k = 0; for (i = 0; i n; i+)/对映射数组赋初值0 sortResulti = 0; for (i = 0; i n; i+) float temp = tempArrayi; index = i; /找到最大的效益并保存此时的下标 for (j = 0; j n; j+) if (temp tempArrayj) & (sortResultj = 0) temp = tempArrayj; index = j; /对wi作标记排序 if (sortResultindex = 0) sortResultindex = +k; /修改效益最低的sortResulti标记 for (i = 0; i n; i+) if (sortResulti = 0) sortResulti = +k; return; /得到本算法的所有输入信息 void getData(float p, float w, int *n) int i = 0; printf(please input the total count of object: ); scanf(%d, n); printf(Please input array of p :n); for (i = 0; i (*n); i+) scanf(%f, &pi); printf(Now please input array of w :n); for (i = 0; i (*n); i+) scanf(%f, &wi); return; void output(float x, int n) int i; printf(nnafter arithmetic data: advise methodn); for (i = 0; i n; i+) printf(x%dt, i); printf(n); for (i = 0; i n; i+) printf(%2.3ft, xi); return; void