#include<stdio.h> #define MAX 200typedef struct Solution {float x[MAX]; //表示該號物品放在多少背包里int order[MAX];//表示物品的序號，相當其名字}Solution;Solution X; int m=15;//背包容量 int n=7;//物品數量 int p[]={10,5,15,7,6,18,3}; int w[]={2,3,5,7,1,4,1};void GreedyKnapsack(int weight[]){float cu;int i;cu=float(m);for(i=0;i<n;i++){if(weight[i]>cu)break;X.x[i]=1;cu=cu-weight[i];}if(i<n){X.x[i]=cu/weight[i];} } //按價值排序 bool compare1(int i,int j){if((p[i]<p[j]))return true;else return false; } //按重量排序 bool compare2(int i,int j){if((w[i]>w[j]))return true;else return false; }// 按價值/重量排序 bool compare3(int i,int j){if((float)(p[i]/w[i]<p[i]/w[j]))return true;else return false; } void swap(int &a,int &b){int t=a;a=b;b=t; }void sort(int type){int i,j;for(i=0;i<n-1;i++){int k=i;for(j=i+1;j<n;j++){if(type==1){if(compare1(k,j))k=j;}else if(type==2){if(compare2(k,j))k=j;}else{if (compare3(k,j))k=j; }if(k!=i){swap(p[i],p[k]);swap(w[i],w[k]);swap(X.order[i],X.order[k]);}}} }void init(){for(int i=0;i<n;i++){X.order[i]=i;X.x[i]=0;} }void show() {float total=0,weight=0;for(int i=0;i<n;i++){total+=p[i]*X.x[i];weight+=w[i]*X.x[i];printf("裝入的包的序號:%d 裝入的份量%.6f\n",X.order[i],X.x[i]);printf("\n 背包的總價值 fp:%.2f,背包的總質量 fw:%.2f\n",total,weight);} } void main() {for(int i=1;i<=3;i++){printf("\t\t 策略%d:\n",i);printf("解向量 x%d:\n",i);init();sort(i);GreedyKnapsack(w);show();} }

總結

以上是生活随笔為你收集整理的c语言-背包问题贪心算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。