学步园

 利用贪心算法解决0/1背包问题时，需要确定装入的原则，大致可分三类：按重量的大小，按价值的大小，按价值与重量比的大小来确定装入的顺序。

设有5个物品，重量分别为 2 2 6 5 4 ，价值分别为 6 3 5 4 6，背包的最大容量为 10。

1. 按重量从小到大装入时：

   可装入第1 2 5 三个物品， 价值为 15

2.按价值从大到小装入时：

  可装入第1 5  2 三个物品，价值为 15

3.按价值至重量比装入时：

  可装入第1 2 5 三个物品，价值为 15

一般按价值重量比装入时，算法要优一些（本人举例欠佳），程序实现如下：

#include <stdio.h>

#define N 5
#define M 10

typedef struct
{
 int num;
 int w;
 int p;
 double v;
 int s;
}item;

void sort(item a[], int n)
{
 int i, j;
 item temp;

 for (i = 0; i < n; i++)
 {
  for (j = i; j < n; j++)
  {
   if (a[i].v < a[j].v)
   {
    
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
   }
  }
 }
}

int main(void)
{
 item a[N] = {{1, 2, 6, 0, 0}, {2, 2, 3, 0, 0}, {3, 6, 5, 0, 0},
 {4, 5, 4, 0, 0}, {5, 4, 6, 0, 0}};
 int i = 0;
 int m = M;
 int V = 0;

 for (i = 0; i < N; i++)
 {
  a[i].v = (double)a[i].p / a[i].w;
 }

 sort(a, N);

 for (i = 0; i < N; i++)
 {
  if (a[i].w <= m)
  {
   a[i].s = 1;
   m = m - a[i].w;
   V = V + a[i].p;
  }
 }
 
 printf("装入的物品重量为: %d,    价值为: %d\n",M-m, V);
 printf("选中的物品编号分别为： ");

 for (i = 0; i < N; i++)
 {
  if (1 == a[i].s)
   printf(" %d ", a[i].num);
 }
 printf("\n");

 return 0;
}