• 注册
  • 关于作者
    企业认证:趣记站长
    关注 6 粉丝 4 喜欢 9 内容 992
    江西省·南昌市
    聊天 送礼
    • 查看作者
    • 贪心算法在背包中的应用

          实现这个算法是学习算法分析与设计这门课程的需要。

          贪心算法是所接触到的第一类算法。算法从局部的最优出发,简单而快捷。对于一个问题的最

      优解只能用穷举法得到时,用贪心法是寻找问题次优解的较好算法。

          贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行,根据某个

      优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一

      步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可

      行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。这种能够

      得到某种度量意义下的最优解的分级处理方法称为贪心法。

          选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。

          假定有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<=xi<=1,pi>0,1<=i<=n.这个问题称为背包问题(Knapsack problem)。

          要想得到最优解,就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说,总应该把那

      些单位效益最高的物体先放入背包。

          在实现算法的程序中,实现算法的核心程序倒没碰到很大的问题,然而实现寻找最优度量标准

      程序时麻烦不断!

          在寻找最优度量标准时,大致方向是用冒泡排序算法。也就是根据p[i]/w[i]的大小来对w[i]来

      排序。

          在直接用此算法时,

      ASP.Net生成静态HTML页
      ASP.NET中的代码分离,探索ASP.NET中Tailspin TravelUI层奥秘,在Asp.net MVC中使用Repeater,ASP.NET中实现模版的动态加载,探讨ASP.NET MVC框架内置AJAX支持编程技术,Asp.net中防止用户多次登录的方法,asp.net的MVC编程、MV编程以及URL重写,ASP.NET图片盗链问题,ASP.NET缓存:方法分析和实践示例,ASP.NET 仿MSN Messenger Alert的弹出窗口控件,ASP.NET中利用VWD操作数据库,Asp.Net中带图片的重填按钮,asp.net 2.0 TreeView客户端个性化控制,如何在.Net 中把图片存入数据库,ASP.NET AJAX框架开发幻灯片播放网页,ASP.NET AJAX框架开发幻灯片播放网页,asp.net在线压缩和解压缩的实现,ASP.NET的Postback,Asp.net中服务端控件事件是如何触发的,ASP.NET创建文件并写入内容
      ASP.net

      可以有如下的一段代码:

          //根据效益tempArray[i]对重量w[i]排序,为进入贪心算法作准备

      1   void sort(float tempArray[], flaot w[], int n)

      2   {

      3       int i = 0, j = 0;

      4       int index = 0;

      5    

      6       //用类似冒泡排序算法,根据效益p[i]/w[i]对w[i]排序

      7       for (i = 0; i < n; i++)

      8    {

      9           float swapMemory = 0;

      10          float temp;

      11

      12          temp = tempArray[i];

      13          index = i;

      14

      15          for (j = i + 1; j < n; j++)

      16          {           

      17              if (temp < tempArray[j])

      18        {

      19                  temp = tempArray[j];

      20                  index = j;

      21        }

      22       }

      23   

      24          //对w[i]排序

      25          swapMemory = w[index];

      26          w[index] = w[i];

      27          w[i] = swapMemory;

      28      }

      29

      30      return;

      31  }

          然而仔细对算法分析后可以发现,“拿来主义”在这里用不上了!

          对算法的测试用例是p[3] = {25, 24, 15};w[3] = {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

          sortResult[i] is :

          1   -107374176.000000   1   1.600000   2    1.600000

          after arithmetic data: x[i]

          0.000000        0.333333        0.000000  

          可以看到其效益为x[3] = {1.4, 1.6, 1.5},于是在M = 20的情况下,其预想中的输出结果是

      0,1,0.5。然而事实上是不是就这样呢?

          当程序进入此函数经过必要的变量初始化后,进入了外围循环,也就是程序的第7行。第一轮循

      环中,temp = tempArray[0] = 1.4,index = i = 0;程序运行到第15行,也就是进入了内层循环。

      内层循环的主要任务是从第i + 1个元素之后找到一个最大的效益并保存此时的下标。到了第24行后

      ,就开始对w[i]进行排序。

          问题就在这里了!排序后的w[i] = {1.6, 1.6, 1.5},因此对w[i]排序后就既改变了w[i]的原

      有顺序,还改变了w[i]的原来值!

          据此,做出一些修改,得到了如下的一段代码:

      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           sortResult[i] = 0;

      9    }

      10

      11      for (i = 0; i < n; i++)

      12      {

      13          float swapMemory = 0;

      14          float temp;

      15

      16          temp = tempArray[i];

      17          index = i;

      18

      19          for (j = i; j < n; j++)

      20          {           

      21              if ((temp < tempArray[j]) && (sortResult[j] == 0))

      22        {

      23                  temp = tempArray[j];

      24                  index = j;

      25        }

      26       }

      27

      28          if (sortResult[index] == 0)

      29       {

      30              sortResult[index] = ++k;

      31       }

      32      }

      33

      34      for (i = 0; i < n; i++)

      35      {

      36          if (sortResult[i] == 0)

      37       {

      38              sortResult[i] = ++k;

      39       }

      40      }

      41

      42      return;

      43  }

          修改后最大的一个改变是没有继续沿用直接对w[i]排序,而是用w[i]的一个映射数组

      sortResult[i]。sortResult[i]中元素值存放的是根据效益计算得w[i]的大小顺序!这样w[i]原有

      的值和位置都没有改变,从而使算法得以实现!

          至于有没有更好的实现版本,还在探索中!

      #include <stdio.h>

      #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++)//准备输出结果

          {

              x[i] = 0;

          }

          for (i = 0; i < n; i++)

          {

              temp = sortResult[i];//得到取物体的顺序

              if (w[temp] > cu)   

              {

                  break;

              }

              x[temp] = 1;//若合适则取出

              cu -= w[temp];//将容量相应的改变

          }

          if (i <= n)//使背包充满

          {

              x[temp] = cu / w[temp];

          }

          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

          {

              sortResult[i] = 0;

          }

          for (i = 0; i < n; i++)

          {

              float temp = tempArray[i];

              index = i;

              //找到最大的效益并保存此时的下标

              for (j = 0; j < n; j++)

              {           

                  if ((temp < tempArray[j]) && (sortResult[j] == 0))

                  {

                      temp = tempArray[j];

                      index = j;

                  }

              }

              //对w[i]作标记排序

              if (sortResult[index] == 0)

              {

                  sortResult[index] = ++k;

              }

          }

          //修改效益最低的sortResult[i]标记

          for (i = 0; i < n; i++)

          {

              if (sortResult[i] == 0)

              {

                  sortResult[i] = ++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", &p[i]);

          }

          printf("Now please input array of w :\n");

          for (i = 0; i < (*n); i++)

          {

              scanf("%f", &w[i]);

          }

          return;

      }

      void output(float x[], int n)

      {

          int i;

          printf("\n\nafter arithmetic data: advise method\n");

          for (i = 0; i < n; i++)

          {

              printf("x[%d]\t", i);

          }

          printf("\n");

          for (i = 0; i < n; i++)

          {

              printf("%2.3f\t", x[i]);

          }

          return;

      }

      void main()

      {

          float p[MAXSIZE], w[MAXSIZE], x[MAXSIZE];

          int i = 0, n = 0;

          int sortResult[MAXSIZE];

          getData(p, w, &n);

          for (i = 0; i < n; i++)

          {

              x[i] = p[i] / w[i];

          }

          sort(x, sortResult, n);

          GREEDY(w, x, sortResult, n);

          output(x, n);

          getch();

      }

      ASP.NET 设计中的 N 个技巧
      ASP.NET中的代码分离,探索ASP.NET中Tailspin TravelUI层奥秘,在Asp.net MVC中使用Repeater,ASP.NET中实现模版的动态加载,探讨ASP.NET MVC框架内置AJAX支持编程技术,Asp.net中防止用户多次登录的方法,asp.net的MVC编程、MV编程以及URL重写,ASP.NET图片盗链问题,ASP.NET缓存:方法分析和实践示例,ASP.NET 仿MSN Messenger Alert的弹出窗口控件,ASP.NET中利用VWD操作数据库,Asp.Net中带图片的重填按钮,asp.net 2.0 TreeView客户端个性化控制,如何在.Net 中把图片存入数据库,ASP.NET AJAX框架开发幻灯片播放网页,ASP.NET AJAX框架开发幻灯片播放网页,asp.net在线压缩和解压缩的实现,ASP.NET的Postback,Asp.net中服务端控件事件是如何触发的,ASP.NET创建文件并写入内容
      ASP.net

    • 0
    • 0
    • 0
    • 58
    • 单栏布局 侧栏位置: