貪心算法解決0 1背包問題

貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

[cpp]
#include <stdio.h>  
#define M 5  
 
struct node{ 
  float value; 
  float weight; 
  int flag; 
}Node[M],temp; 
float Value,curvalue=0; 
float Weight,curweight=0; 
 
//按性價比排序  
void sort(){ 
     int i,j; 
     for(i=0;i<M-1;i++){ 
         for(j=i+1;j<M;j++){ 
             if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight){ 
                temp=Node[i]; 
                Node[i]=Node[j]; 
                Node[j]=temp; 
             } 
         } 
     } 
} 
 
//裝載主要方法  
void load(){ 
    int i; 
    for(i=0;i<M;i++){ 
        if((Node[i].weight+curweight)<=Weight){ 
         curvalue+=Node[i].value; 
         curweight+=Node[i].weight; 
         Node[i].flag=1; 
        }else{ 
         Node[i].flag=0; 
        }    
    } 
} 
 
//進行結果的輸出  
void putout(){ 
    int i; 
    printf("選中物品的重量分別為："); 
    for(i=0;i<M;i++){ 
        if(Node[i].flag){ 
          printf("%.2f ",Node[i].weight); 
        } 
    } 
    printf("\n總價值為:%.2f",curvalue); 
} 
 
 
int main(){ 
    int i; 
    printf("請輸入物品的重量和價值：\n"); 
    for(i=0;i<M;i++){ 
       printf("請輸入第%d個物品的重量和價值",i+1); 
       scanf("%f%f",&Node[i].weight,&Node[i].value); 
    } 
    printf("\n請輸入背包容積："); 
    scanf("%f",&Weight); 
    sort(); 
    load(); 
    putout(); 
  return 0; 
} 

#include <stdio.h>
#define M 5

struct node{
  float value;
  float weight;
  int flag;
}Node[M],temp;
float Value,curvalue=0;
float Weight,curweight=0;

//按性價比排序
void sort(){
     int i,j;
  for(i=0;i<M-1;i++){
   for(j=i+1;j<M;j++){
    if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight){
       temp=Node[i];
    Node[i]=Node[j];
    Node[j]=temp;
    }
   }
  }
}

//裝載主要方法
void load(){
 int i;
 for(i=0;i<M;i++){
  if((Node[i].weight+curweight)<=Weight){
   curvalue+=Node[i].value;
   curweight+=Node[i].weight;
   Node[i].flag=1;
  }else{
   Node[i].flag=0;
  } 
 }
}

//進行結果的輸出
void putout(){
 int i;
 printf("選中物品的重量分別為：");
 for(i=0;i<M;i++){
   if(Node[i].flag){
          printf("%.2f ",Node[i].weight);
  }
 }
 printf("\n總價值為:%.2f",curvalue);
}

int main(){
 int i;
 printf("請輸入物品的重量和價值：\n");
 for(i=0;i<M;i++){
    printf("請輸入第%d個物品的重量和價值",i+1);
    scanf("%f%f",&Node[i].weight,&Node[i].value);
 }
 printf("\n請輸入背包容積：");
 scanf("%f",&Weight);
 sort();
 load();
 putout();
  return 0;
}