完全背包问题（贪婪法）

// Knap.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define N 100
#define MAX_WEIGHT 100
typedef struct {
  int weight;
  int price;
  float v;
}Object;

int getPrice(){
   int a;
   a = rand()%100;
   if(0==a)
    return 1;
   else
    return a;
}

int getWeight(){
   int a;
   a = rand()%100;
   if(0==a)
    return 1;
   else
    return a;
}

void BubbleSort(Object a[]){
 Object t; Object *tp;
 Object *p1; Object *p2;
 p1 = &a[0];  tp = &t;
 for(int i=0;i<N -1;i++){
  for(int j=0;j<N-i-1;j++){
   if(a[j+1].v > a[j].v){
      tp = &t;
      p1 = &a[j+1];
      p2 = &a[j];

      tp->price = p2->price;
      tp->v = p2->v;
      tp->weight = p2->weight;
     
      p2->price = p1->price;
      p2->weight = p1->weight;
      p2->v = p1->v;
             

      p1->price = tp->price;
      p1->v = tp->v;
      p1->weight = tp->weight;
   
   }
  }
 }
  
}

/*

1. 根据各个物体的价值p与重量w计算价值重量比v
2. 根据v降序排序
3. 从当前最大的v的开始，判断该物体重量是否超过背包剩余载重
4. 是则放入背包剩余载重量的物体，加上这部分的价值，跳到7
5. 否则将物体完整放入背包，加上物体的价值
6. 若还有物体未放入背包，则跳到3
7. 输出背包中物体的总价值
*/

void print(Object o[]){
 for(int i=0;i<N;i++){

   printf("rate:%4.6f,price:%d,weight:%d \n",o[i].v,o[i].price,o[i].weight);
 }
}

int main(int argc, char* argv[])
{
 Object obj[N];float k;
 srand((unsigned)time(NULL));
    for(int i=0;i<N;i++){
    obj[i].weight = getWeight();
    obj[i].price =  getPrice();
    obj[i].v = obj[i].price / obj[i].weight  ;

 }
    BubbleSort(obj);
    print(obj);
   
 //int now_weight=0;
 Object max;
 max.weight =0 ;
 max.price =0;

 int count=0;
 int m =0;
 while(obj[m].weight<=MAX_WEIGHT-max.weight){  
  max.weight += obj[m].weight;
  max.price += obj[m].price;
  printf("%d,%d \n",MAX_WEIGHT-max.weight, max.weight);
  m++;
  count++;
 }
 
 printf("MAX PRICE IS ::::%d,%d,%d\n",max.weight,max.price,count);

// printf("%d \n",rand()%100);
 return 0;
}

 

原理是网上找的。