贪心算法实现01背包问题.doc

《贪心算法实现01背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪心算法实现01背包问题算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。具体实现过程是：首先可以设置一个备份pvu类型的数组，在不破环原数据的情况下，对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i，j(其中i表示当前应该参与最佳pv值的元素指针，j表示符合约束条件的指针（单位重量价值PV最大，重量最小，不超过最大承重量约束)代码实现如下：#includeusingnamespacest

2、d;typedefstruct{intv;intw;floatpv;}pvu;voidsortByPv(pvu[],int);intzeroneBags(pvu[],int,int,int*);voidprint(pvua[],intn){for(inti=0;i

3、sizeof(w)/sizeof(int);constintN=n;pvuarr[N];for(i=0;i>maxw;cout<<"最大价值为:"<

4、tByPv(pvuarr[],intn){pvut;inti,j;for(i=0;i

5、vail&&iarr[j].w&&j>i){minw=j;}}if(arr[minw].w<=avail){avail-=arr[minw].w;totalv+=arr[minw].v;i++;}elsei++;}*e=avail;returntotalv;}运行结果截图：