贪心算法入门
贪心算法例题:
代码:
/* 取糖果 输入:4 15 //四箱,能装的重量为15 //价值,重量 100 4 412 8 266 7 591 2 输出: 1193.0 */ #include<iostream> #include<algorithm> using namespace std; struct candy{ double v,m;//v是价值,m是重量 }candies[100]; bool bmp(candy &a,candy &b){ return (a.v/a.m)>(b.v/b.m); } int main(){ int n,i; double sum; double value=0; cout<<"请输入糖果箱数n"<<endl; cin>>n; cout<<"请输入能容纳的总重量"<<endl; cin>>sum; for(i=1;i<=n;i++) cin>>candies[i].v>>candies[i].m; sort(candies+1,candies+1+n,bmp); for(i=1;i<=n;i++) cout<<candies[i].v<<" "; for(i=1;i<=n;i++) { if(sum>=candies[i].m)//看能否全装 { value=value+candies[i].v; sum=sum-candies[i].m; } else //需要分装 { value=value+sum*(candies[i].v/candies[i].m); break; } } cout<<value<<endl; return 0; }
总结:
贪心算法通过每一步最优,来达到总体最优。(有时候贪心算法不一定能取到最优解)