贪心算法之最优装载问题

问题描述: 给出n个物体,第i个物体的重量是Wi,选择尽量多的物体,使得总重量不超过C.
问题分析: 这是一个很典型的用贪心算法的题目.要想让装的物体越多,自然装的最轻的物体就越多.因此可以对物体的重量由小到大进行排序,然后依次装载即可.这就体现了贪心算法只顾眼前,但却可以得到最优解.
解决问题: 代码如下

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h> //为了引入memcpy
 4 /* 最有最优装载问题:
 5    给出n个物体,第i个物体的重量为Wi,选择更多的物体,是物体的总量不超过C
 6  */
 7  void swap(int *a,int *b)
 8  {
 9      int temp;
10      temp = *a;
11      *a = *b;
12      *b = temp;
13  }
14  // 采用选择法对重量进行排序,t中记录的是从小到大的包的索引
15  void sortweight(int *w,int *t,int n)
16  {
17      int i,j,temp;
18      int *w1 = malloc(sizeof(int)*n);
19      for(i =0; i < n; ++i)
20      {
21         t[i] = i;
22         w1[i] = w[i];
23      }
24      for(i = 0; i < n; ++i)
25      {
26          temp = i;
27          for(j = i+1; j < n; ++j)
28          {
29              if(w1[j] < w1[temp])
30                 temp = j;
31          }
32          if(temp != i)
33          {
34               swap(&w1[i],&w1[temp]); // 这个数据交换是必须的
35               swap(&t[i],&t[temp]);
36          }
37      }
38  }
39 int main()
40 {
41     int n,weight_max,i;
42     int *w,*ind,*res;
43 
44     printf("请输入商品的数量和商品的总载量
");
45     scanf("%d %d",&n,&weight_max);
46 
47     w = malloc(sizeof(int)*n);
48     ind = malloc(sizeof(int)*n);
49     res = malloc(sizeof(int)*n);
50 
51     printf("请依次输入商品的重量
");
52     for(i = 0; i < n; ++i)
53         scanf("%d",&w[i]);
54 
55     sortweight(w,ind,n);
56 
57     for(i = 0; i < n && w[ind[i]] <= weight_max; ++i)
58     {
59         res[ind[i]] = 1;
60         weight_max -= w[ind[i]];
61     }
62     printf("贪心算法求解后的结果是:
");
63     for(i = 0; i < n; ++i)
64     {
65         printf("%d ",res[i]);
66     }
67     printf("
");
68     return 0;
69 }

4. 程序分析: 由于不要改变原始物体重量的值,所以在排序的时候要另外再开辟一个数组存储重量.并且另外开辟ind[]存放索引记录装载的顺序.ind[]存放的是重量数组中每个元素在这组数组中大小的顺序(索引).怎样在排序时记录索引需要在练习排序的时候注意下.

5. 学习参考资料:http://blog.csdn.net/liufeng_king/article/details/8711928