贪心算法实现01背包问题

贪心算法实现01背包问题算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。具体实现过程是：首先可以设置一个备份pvu类型的数组，在不破环原数据的情况下，对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i，j(其中i表示当前应该参与最佳pv值的元素指针，j表示符合约束条件的指针（单位重量价值PV最大，重量最小，不超过最大承重量约束)代码实现如下：#includeiostreamusingnamespacestd;typedefstruct{intv;intw;floatpv;}pvu;voidsortByPv(pvu[],int);intzeroneBags(pvu[],int,int,int*);voidprint(pvua[],intn){for(inti=0;in;i++){couta[i].wa[i].va[i].pvendl;}coutendl;}intmain(){inti,maxw;intw[]={1,2,3,2};intv[]={9,10,15,6};intn=sizeof(w)/sizeof(int);constintN=n;pvuarr[N];for(i=0;in;i++){arr[i].v=v[i];arr[i].w=w[i];arr[i].pv=v[i]*1.0/w[i];}intremained;cout输入背包的最大承重量:\n;cinmaxw;cout最大价值为:zeroneBags(arr,n,maxw,&remained)\n还剩remained公斤空间未使用endl;return0;}voidsortByPv(pvuarr[],intn){pvut;inti,j;for(i=0;in-1;i++)for(j=0;jn-1-i;j++)if(arr[j].pvarr[j+1].pv){t=arr[j];arr[j]=arr[j+1];arr[j+1]=t;}}intzeroneBags(pvuarr[],intn,intmaxw,int*e){inti=0,j,minw,totalv=0;intavail=maxw;sortByPv(arr,n);//按最大单位重量价值PV从大到小的排序while(avail&&in){minw=i;for(j=0;jn;j++)if(arr[i].pv==arr[j].pv){if(arr[i].warr[j].w&&ji){minw=j;}}if(arr[minw].w=avail){avail-=arr[minw].w;totalv+=arr[minw].v;i++;}elsei++;}*e=avail;returntotalv;}运行结果截图：