贪心算法-背包问题

#include<stdio.h> #define N 5 //物品数量(总类) #define W 100 //容量 int v_temp[N+1], w_temp[N+1]; // 物品价值数组，物品容量数组 double vw_temp[N+1];//单位物品价值容量数组 double answer[N+1] = {0};//解方案数组 void show(int v[],int w[],double vw[]) { int i; for(i = 1;i<=N;i++){ printf("%d ",v[i]); } printf("\n"); for(i = 1;i<=N;i++){ printf("%d ",w[i]); } printf("\n"); for(i = 1;i<=N;i++){ printf("%.1f ",vw[i]); } printf("\n"); } void merge_sort(int v[],int w[],double vw[],int l,int r) { if(l>=r) { return ; } int mid = (l+r)/2; merge_sort(v,w,vw,l,mid); merge_sort(v,w,vw,mid+1,r); int i = l,j = mid+1,k = 1; while(i<=mid && j<=r) { if(vw[i] > vw[j]) { vw_temp[k] = vw[i]; v_temp[k] = v[i]; w_temp[k] = w[i]; k++,i++; } else { vw_temp[k] = vw[j]; v_temp[k] = v[j]; w_temp[k] = w[j]; k++,j++; } } while(i<=mid) { vw_temp[k] = vw[i]; v_temp[k] = v[i]; w_temp[k] = w[i]; k++,i++; } while(j<=r) { vw_temp[k] = vw[j]; v_temp[k] = v[j]; w_temp[k] = w[j]; k++,j++; } for(i = l,j= 1;i<=r;i++,j++) { vw[i] = vw_temp[j]; v[i] = v_temp[j]; w[i] = w_temp[j]; } } double max_value(int v[],int w[],double vw[]) { double result = 0.0; int i,w_temp = W; for(i = 1;i<=N;i++) { if(w_temp>w[i]) { answer[i] = 1; result = result+v[i]; w_temp = w_temp-w[i]; } else { break; } } if(w_temp>0 && i<=N) { answer[i] = (double)w_temp/w[i]; result = result + w_temp*vw[i]; } return result; } int main() { int v[] = {0,20,65,30,40,60};//物品价值数组 int w[] = {0,10,30,20,40,50};//物品容量数组 double vw[N+1] = {0}; int i; for(i = 1;i<=N;i++) { vw[i] = (double)v[i]/w[i]; } printf("排序前\n"); show(v,w,vw); printf("排序后\n"); merge_sort(v,w,vw,1,N);//归并排序 show(v,w,vw); double result = max_value(v,w,vw); printf("result = %.1f\n",result); printf("解方案结果为:\n"); for(i = 1;i<=N;i++) { printf("%.1f ",answer[i]); } return 0; }