贪心算法实现代码

贪心算法通常没有一个固定的实现方式，因为它是根据问题的特殊性质来设计的。下面是一个简单的贪心算法实现代码，以解决背包问题为例：

#include<bits/stdc++.h>
using namespace std;

struct Goods{
    int w;
    int v;
    double ratio;   //性价比
    bool operator <(const Goods& g)const{
        return ratio>g.ratio;
    }
};

Goods goods[100];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>goods[i].w>>goods[i].v;
        goods[i].ratio=1.0*goods[i].v/goods[i].w;
    }

    sort(goods,goods+n);

    double ans=0.0;
    for(int i=0;i<n;i++){
        if(m>=goods[i].w){
            ans+=goods[i].v;
            m-=goods[i].w;
        }else{
            ans+=m*goods[i].ratio;
            break;
        }
    }

    printf("%.2f",ans);
    return 0;
}

这段代码实现了一个简单的贪心算法，用于解决背包问题。在这个问题中，我们需要选择一些物品放入一个容量为 $m$ 的背包中，使得背包中的物品总价值最大。我们定义每个物品的价值为 $v_i$，重量为 $w_i$，性价比为 $v_i/w_i$。我们将物品按照性价比从高到低排序，然后依次将性价比高的物品放入背包中，直到背包装不下为止。如果当前物品不能完全装入背包，我们可以选择部分装入，以达到最优解。