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

会计考友

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

会计考友

　　18 {
0 ~9 S' i' f7 _& i  A0 z% h* Q# ]　　19 temp = tempArray[j];
% H! J2 b% o$ P　　20 index = j;
; f/ m+ W' @8 e2 J7 ~　　21 }
　　22 }
2 q: r5 Q2 z# Q3 X0 ]　　23
, W& r  ~" e: Q9 b　　24 //对w排序
　　25 swapMemory = w[index];
0 p2 X, [( i+ x1 ~) j' L& t( v$ X　　26 w[index] = w;
　　27 w = swapMemory;
　　28 }
! t: I  `+ s+ J2 r5 J- R# s　　29
　　30 return;
! j7 ]+ n0 `9 b& V* u6 E" h　　31 }
* ?: a/ F" V4 M5 ]1 b　　然而仔细对算法分析后可以发现，“拿来主义”在这里用不上了!
　　对算法的测试用例是p[3] = {25, 24, 15};w[3] = {18, 15, 10}。得到的结果如下：
. J; q6 l, ]/ y0 k　　please input the total count of object: 3
　　Please input array of p :
　　25 24 15
9 v5 Z! V* Q5 i! p　　Now please input array of w :
　　18 15 10
　　sortResult is :
　　1 -107374176.000000 1 1.600000 2 1.600000
　　after arithmetic data: x
　　0.000000 0.333333 0.000000
8 c0 d. |; w- F/ v6 t3 T2 X, \　　可以看到其效益为x[3] = {1.4, 1.6, 1.5}，于是在M = 20的情况下，其预想中的输出结果是0，1，0.5。然而事实上是不是就这样呢?
　　当程序进入此函数经过必要的变量初始化后，进入了外围循环，也就是程序的第7行。第一轮循环中，temp = tempArray[0] = 1.4,index = i = 0;程序运行到第15行，也就是进入了内层循环。
; A. b( B' m# S0 N3 C0 ?　　内层循环的主要任务是从第i + 1个元素之后找到一个最大的效益并保存此时的下标。到了第24行后，就开始对w进行排序。
& w: y' z  \1 W0 C: h　　问题就在这里了!排序后的w = {1.6, 1.6, 1.5}，因此对w排序后就既改变了w的原有顺序，还改变了w的原来值!
6 J! w, H  I/ Q9 R6 b5 k1 C8 B, {' Z　　据此，做出一些修改，得到了如下的一段代码：
　　1 void sort(float tempArray[], int sortResult[], int n)
  k" |; K' C! E+ w4 ?  m& e6 s4 U% k　　2 {
　　3 int i = 0, j = 0;
, j$ A4 t7 T8 q: @　　4 int index = 0, k = 0;
* W) a! Z0 u" O( G　　5
, y& w/ H! M4 H; C* {　　6 for (i = 0; i < n; i++)//对映射数组赋初值0
　　7 {
　　8 sortResult = 0;
　　9 }
: K( b7 T" N2 A0 J2 Y) O/ a2 @　　10
　　11 for (i = 0; i < n; i++)

会计考友

　12 {　　13 float swapMemory = 0;
$ ]  m; X/ _% w4 d- g　　14 float temp;
5 T$ D4 h, }7 e0 W( C　　15
& i1 r8 S  t) g# r9 D# n. r　　16 temp = tempArray;
+ w  t+ b6 a3 @6 `' J3 q　　17 index = i;
　　18
: o+ [) L* G( y4 u3 K　　19 for (j = i; j < n; j++)
# Z# q+ ]! {3 _" p　　20 {
　　21 if ((temp < tempArray[j]) && (sortResult[j] == 0))
, ]& P, B* |) k" t$ k　　22 {
- \6 Q) M+ p; J. v6 d: G  p  n& ?　　23 temp = tempArray[j];
, s0 o, H& I* p　　24 index = j;
　　25 }
. _0 W5 K- M- s2 q% E# @　　26 }
　　27
　　28 if (sortResult[index] == 0)
　　29 {
　　30 sortResult[index] = ++k;
　　31 }
  _) O5 d4 t/ j5 X# B4 F　　32 }
2 U* p2 D9 X3 _* Z9 R% x: V　　33
　　34 for (i = 0; i < n; i++)
4 }5 D  F6 h* c/ w" n　　35 {
/ M$ H2 Y- z5 l/ J" x" H　　36 if (sortResult == 0)
　　37 {
5 b% A4 ~1 j: U( t& `  k" B+ r# j　　38 sortResult = ++k;
　　39 }
　　40 }
$ ^3 r$ f3 e/ Q0 o% b0 e　　41
' k+ i. s  |9 m& S　　42 return;
　　43 }
8 _" U+ C/ D, O　　修改后最大的一个改变是没有继续沿用直接对w排序，而是用w的一个映射数组sortResult。sortResult中元素值存放的是根据效益计算得w的大小顺序!这样w原有的值和位置都没有改变，从而使算法得以实现!
( ?, I& j$ c: h　　至于有没有更好的实现版本，还在探索中!
　　#include

会计考友

　#define MAXSIZE 100 //假设物体总数　　#define M 20 //背包的载荷能力
　　//算法核心，贪心算法
3 R8 P* b9 o9 S9 w8 y5 l5 H" ^　　void GREEDY(float w[], float x[], int sortResult[], int n)
　　{
! C' K2 x- j0 Q8 @' O　　float cu = M;
! ^) \9 L/ x3 t: h; _' c　　int i = 0;
  U% w2 \8 ^4 T- F1 ^　　int temp = 0;
　　for (i = 0; i < n; i++)//准备输出结果
7 |. ~& ^0 k! E5 y. J　　{
　　x = 0;
+ J2 c$ N4 T# N　　}
3 b0 o9 v# U1 v$ w1 G" B) k4 u2 L　　for (i = 0; i < n; i++)
　　{
　　temp = sortResult;//得到取物体的顺序
　　if (w[temp] > cu)
　　{
　　break;
0 Z3 r0 h8 m# n　　}
　　x[temp] = 1;//若合适则取出
. V4 k6 ~6 k) C& A! d- r) r/ c% o　　cu -= w[temp];//将容量相应的改变
2 I; \* C* Q6 {, y( |! d! {　　}
* ?$ E1 v: r& p" R6 r' a
* p& }# O  L; m6 Y* \　　if (i

会计考友

{　　if ((temp < tempArray[j]) && (sortResult[j] == 0))
　　{
! b! W5 u+ o, d) B/ `　　temp = tempArray[j];
' R$ n! `2 F+ v8 G1 a　　index = j;
　　}
4 g8 F: z9 D! U　　}
　　//对w作标记排序
　　if (sortResult[index] == 0)
: ^/ K4 e3 l, t" H% P, A6 f　　{
　　sortResult[index] = ++k;
3 W$ S; Y: g/ ]7 L6 u7 M+ `　　}
　　}
　　//修改效益最低的sortResult标记
0 f! D" l3 P; C. f( {7 E　　for (i = 0; i < n; i++)
　　{
9 X7 l8 p4 I; u　　if (sortResult == 0)
　　{
　　sortResult = ++k;
　　}
' J7 |6 V3 k+ M) {2 V/ Z; f' K　　}
+ g# `- g% C2 r9 D" c1 `* j　　return;
# L% Z5 e. D" ~; b  R0 w4 C　　}
　　//得到本算法的所有输入信息
　　void getData(float p[], float w[], int *n)
1 R0 p! z" a3 f. W/ }/ ?7 p# O) E　　{
　　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++)
　　{
' T& L6 @; X+ p　　scanf("%f", &p);

会计考友

　　}
/ Q! q4 f' l5 R8 I" \8 u　　printf("Now please input array of w :\n");
: z+ f+ h& M4 h, {　　for (i = 0; i < (*n); i++)
　　{
9 O) X% b" _+ F　　scanf("%f", &w);
　　}
　　return;
　　}
; j5 M4 G# V+ u6 v　　void output(float x[], int n)
　　{
　　int i;
　　printf("\n\nafter arithmetic data: advise method\n");
0 b9 W9 q! X4 u7 c2 y( Z　　for (i = 0; i < n; i++)
　　{
　　printf("x[%d]\t", i);
! n8 ]. p3 u- o  c) b+ F% V　　}
3 r% S, A+ V1 u' U. A( w4 t. o1 U　　printf("\n");
, @7 g/ z+ o% q5 O　　for (i = 0; i < n; i++)
　　{
　　printf("%2.3f\t", x);
+ [1 }# R7 e# n( @$ }: q　　}
　　return;
& k. ]$ \1 c- O% v! W　　}
　　void main()
　　{
　　float p[MAXSIZE], w[MAXSIZE], x[MAXSIZE];
　　int i = 0, n = 0;
2 Q) Z4 C( x' R$ n8 M　　int sortResult[MAXSIZE];
　　getData(p, w, &n);
　　for (i = 0; i < n; i++)
　　{
4 W0 ]9 g9 z8 O5 h　　x = p / w;
　　}
) d, T7 c0 p8 [$ |6 V& J　　sort(x, sortResult, n);
　　GREEDY(w, x, sortResult, n);
. k, {% X) A3 H4 v  q　　output(x, n);
, ?% a8 w; K, Z) R　　getch();
　　}