贪心算法思想

    贪心算法，就是总是做出在当前看来是最好的选择的一种方法。

    贪心算法，具备如下的性质：

    1.贪心选择性质；2.最优子结构性质；

    有一批集装箱要装入一个载质量为C的货船，每个集装箱的质量由用户自己输入指定，在货物的装载体积不限的前提下，如何装载集装箱才能尽可能多地将集装箱装入货船中。

#include <stdio.h>

void sort(int w[], int t[], int n)
{
  int i,j,tmp;
  int *w_tmp = (int *)malloc(sizeof(int) * n);

  for(i=0;i<n;i++)
  {
    t[i] = i;
  }
  for(i=0;i<n;i++)
  {
    w_tmp[i] = w[i];
  }
  for(i=0;i<n-1;i++)
  {
    for(j=0;j<n-i-1;j++)
    {
      if(w_tmp[j] > w_tmp[j+1])
      {
        tmp = w_tmp[j];
        w_tmp[j] = w_tmp[j+1];
        w_tmp[j+1] = tmp;
        tmp = t[j];
        t[j] = t[j+1];
        t[j+1] = tmp;
      }
    }
  }
}

void loading(int x[], int w[], int c, int n)
{
  int i,s = 0;
  int *t = (int *) malloc(sizeof(int) * n);
  sort(w,t,n);
  for(i=0;i<n;i++)
  {
    x[i] = 0;
  }

  for(i = 0; i < n && w[t[i]] <= c; i++)
  {
    x[t[i]] = 1;
    c = c - w[t[i]];
  }
}

int main(int argc, char* argv[])
{
  int x[5],w[5],c,i;
  printf("please input the maximum loading of the sheep\n");
  scanf("%d",&c);
  printf("please input the weight of FIVE box\n");
  for(i = 0; i < 5; i++)
  {
    scanf("%d",&w[i]);
  }

  loading(x,w,c,5);
  printf("the following boxes will be loaded\n");
  for(i = 0; i < 5; i++)
  {
    if(x[i] == 1)
    {
      printf("Box:%d ",i);
    }
  }
  printf("\n");
}

执行结果如下：

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./3.8

please input the maximum loading of the sheep

15

please input the weight of FIVE box

2 4 5 6 8

the following boxes will be loaded

Box:0 Box:1 Box:2