2011年计算机等级考试二级C辅导实例编程(3)

会计考友

贪心算法在背包中的应用　　贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，根据某个优化测度(可能是目标函数，也可能不是目标函数)，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。
　　选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。
, l/ G6 {. b: i+ A
　　假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi(1

会计考友

　　18 {
5 Y$ \7 t3 N* @　　19 temp = tempArray[j];
　　20 index = j;
! q* d/ [& ^! E& o　　21 }
7 I  p4 R& |. |5 [　　22 }
　　23
　　24 //对w排序
9 T! N' `; u6 _  m8 P( B) H　　25 swapMemory = w[index];
7 q( }4 _+ @& ]! s3 b! F4 c　　26 w[index] = w;
　　27 w = swapMemory;
　　28 }
　　29
　　30 return;
8 L. q% ?! N: Q* a$ j　　31 }
　　然而仔细对算法分析后可以发现，“拿来主义”在这里用不上了!
　　对算法的测试用例是p[3] = {25, 24, 15};w[3] = {18, 15, 10}。得到的结果如下：
. X' Q; x" p) K7 Y& y( p3 r% _1 e  K　　please input the total count of object: 3
　　Please input array of p :
2 P1 v! S& o. B6 h, u/ ^　　25 24 15
　　Now please input array of w :
$ S+ t4 [, \$ R# W, r& H- W　　18 15 10
1 e1 d8 L6 D' A, k　　sortResult is :
　　1 -107374176.000000 1 1.600000 2 1.600000
　　after arithmetic data: x
　　0.000000 0.333333 0.000000
" z, l- S# r* J" \7 S" h　　可以看到其效益为x[3] = {1.4, 1.6, 1.5}，于是在M = 20的情况下，其预想中的输出结果是0，1，0.5。然而事实上是不是就这样呢?
! Y! }# }0 w; ~' B# n* N- h# `" A$ y5 A　　当程序进入此函数经过必要的变量初始化后，进入了外围循环，也就是程序的第7行。第一轮循环中，temp = tempArray[0] = 1.4,index = i = 0;程序运行到第15行，也就是进入了内层循环。
　　内层循环的主要任务是从第i + 1个元素之后找到一个最大的效益并保存此时的下标。到了第24行后，就开始对w进行排序。
　　问题就在这里了!排序后的w = {1.6, 1.6, 1.5}，因此对w排序后就既改变了w的原有顺序，还改变了w的原来值!
5 k- J. M8 W$ A9 w　　据此，做出一些修改，得到了如下的一段代码：
$ O- |8 V. p$ B6 B- a　　1 void sort(float tempArray[], int sortResult[], int n)
7 h, T  N; |+ y4 a$ J) u. V　　2 {
6 O/ ^& e; L: Y3 v3 R　　3 int i = 0, j = 0;
  ~. |0 H/ R5 G. N  Q% v　　4 int index = 0, k = 0;
　　5
　　6 for (i = 0; i < n; i++)//对映射数组赋初值0
　　7 {
. M- @/ q# R/ v: d9 M8 R　　8 sortResult = 0;
　　9 }
　　10
　　11 for (i = 0; i < n; i++)

会计考友

　12 {　　13 float swapMemory = 0;
　　14 float temp;
, T6 L+ w7 K+ b3 B　　15
# [+ g. @; e; o* u# Q( ]* R9 s  ?　　16 temp = tempArray;
　　17 index = i;
　　18
# j; p2 h4 f- N5 P　　19 for (j = i; j < n; j++)
　　20 {
　　21 if ((temp < tempArray[j]) && (sortResult[j] == 0))
4 @( w2 T5 l1 m# C! Q% V  b　　22 {
　　23 temp = tempArray[j];
　　24 index = j;
　　25 }
2 ~/ ]3 U7 B$ |4 }4 k　　26 }
$ P4 ~2 S! D8 ~. l1 E( a　　27
　　28 if (sortResult[index] == 0)
　　29 {
　　30 sortResult[index] = ++k;
　　31 }
　　32 }
　　33
& _4 O+ S5 G) s) U, V　　34 for (i = 0; i < n; i++)
　　35 {
　　36 if (sortResult == 0)
　　37 {
　　38 sortResult = ++k;
　　39 }
　　40 }
　　41
　　42 return;
- Z$ [4 X; T- b2 s4 F- y* Y9 T　　43 }
8 [! l5 {# v" I. e+ f  f4 i4 B5 G　　修改后最大的一个改变是没有继续沿用直接对w排序，而是用w的一个映射数组sortResult。sortResult中元素值存放的是根据效益计算得w的大小顺序!这样w原有的值和位置都没有改变，从而使算法得以实现!
　　至于有没有更好的实现版本，还在探索中!
　　#include

会计考友

　#define MAXSIZE 100 //假设物体总数　　#define M 20 //背包的载荷能力
　　//算法核心，贪心算法
　　void GREEDY(float w[], float x[], int sortResult[], int n)
( B& Z! V  O# ^' c+ ~, J8 y: d4 m3 }　　{
　　float cu = M;
　　int i = 0;
　　int temp = 0;
　　for (i = 0; i < n; i++)//准备输出结果
& l$ o4 e: e2 B# H7 Q2 |　　{
　　x = 0;
8 L! K" B5 M1 m6 j; `: h　　}
　　for (i = 0; i < n; i++)
　　{
　　temp = sortResult;//得到取物体的顺序
　　if (w[temp] > cu)
7 [- w' S8 Z- R0 ~  u　　{
+ Z9 ~0 u0 u2 R: V! I　　break;
　　}
　　x[temp] = 1;//若合适则取出
　　cu -= w[temp];//将容量相应的改变
6 E9 w/ B2 D% ]. r) y9 E. i　　}
( E9 f; f/ T  X9 `5 ]# L* _
　　if (i

会计考友

{　　if ((temp < tempArray[j]) && (sortResult[j] == 0))
　　{
　　temp = tempArray[j];
　　index = j;
8 l9 l" |  n6 c! {3 T; _  c　　}
　　}
& N8 v; p) X' [9 p  i　　//对w作标记排序
, m3 I9 h- L3 w& B　　if (sortResult[index] == 0)
9 c- G* l  m) C: z　　{
6 ?. r1 c7 H! Z( k　　sortResult[index] = ++k;
　　}
4 H$ w0 N, e/ o5 ^9 `& s! Q　　}
0 l, I# D3 o- E　　//修改效益最低的sortResult标记
& i! x! `- Y' {% g5 D: g　　for (i = 0; i < n; i++)
　　{
& C, a/ y7 A3 x) e" t　　if (sortResult == 0)
/ N9 @# R$ C: u" Z9 B/ K' v　　{
; y* C3 {" v1 m# D　　sortResult = ++k;
, v2 O- e# s. E. n$ u0 ~　　}
　　}
8 `2 O: o& X1 G　　return;
2 W. }1 {' i8 p. U. b& _  W　　}
& O/ R* O9 x! m% D9 y! K, \) |　　//得到本算法的所有输入信息
　　void getData(float p[], float w[], int *n)
9 E# `, V0 U8 f0 w; G' q' w　　{
* A' y; u  l( E1 |　　int i = 0;
% v& z5 V/ D( q1 A' k　　printf("please input the total count of object: ");
4 S# t# w* Q* M& n* E5 D) }　　scanf("%d", n);
  G# u9 P- L& [9 d! m- z9 A3 X/ }　　printf("Please input array of p :\n");
　　for (i = 0; i < (*n); i++)
　　{
, `) [- \7 c8 f' z$ M　　scanf("%f", &p);

会计考友

　　}
　　printf("Now please input array of w :\n");
　　for (i = 0; i < (*n); i++)
　　{
! T1 m. m7 x$ @, W( o3 r: Y2 t　　scanf("%f", &w);
& _+ p0 N5 }4 a' b　　}
　　return;
  _9 `4 e: y, h) {7 y( j$ P2 z　　}
　　void output(float x[], int n)
) n, i2 y# K# @　　{
　　int i;
6 z5 N: `0 v0 K/ h+ I5 G" b5 F　　printf("\n\nafter arithmetic data: advise method\n");
% k; C5 |' f$ D! e- v. l) E　　for (i = 0; i < n; i++)
　　{
/ [5 A7 w7 _: f  [　　printf("x[%d]\t", i);
) V# c6 m2 d% x9 q3 w　　}
　　printf("\n");
9 e3 y: h7 G/ z7 o# x- g( [　　for (i = 0; i < n; i++)
9 }% d+ u, b, q2 g: v　　{
. A. d& C9 u) m) X5 ^　　printf("%2.3f\t", x);
　　}
$ i0 i2 n) |; p# p  p/ N　　return;
* L# _7 ^$ z. @　　}
1 U* H: u6 l0 [　　void main()
　　{
$ j6 J3 {. u) s4 A　　float p[MAXSIZE], w[MAXSIZE], x[MAXSIZE];
. p  i1 A; V9 X: k　　int i = 0, n = 0;
+ I! X6 N; n5 w　　int sortResult[MAXSIZE];
% c  B( w3 P  x% K5 E　　getData(p, w, &n);
　　for (i = 0; i < n; i++)
　　{
　　x = p / w;
+ R) v! O' v$ W. t% z( O　　}
　　sort(x, sortResult, n);
# l4 e! O% W0 y1 I" W　　GREEDY(w, x, sortResult, n);
' Q! i5 [2 Y' z7 ^* f, Z5 D　　output(x, n);
" N2 J3 r4 I' x. m! R6 q. @　　getch();
　　}