日期：2022年5月25日

注：本博客仅供参考

概念与思路

贪心算法是指在对某一问题求解时，总是作出当前情况下的最优选择。因此，贪心算法考虑的不是整个问题的最优解，算法得到的是在某一局部环境下的最优解。

贪心算法的一般思路为：

1. 把要求解的问题分为若干个子问题；
2. 对每个子问题求解，得到子问题的局部最优解；
3. 把得到的局部最优解合为原来问题的一个解。

注意事项（尤为重要）

• 贪心算法能省去要穷尽所有可能二耗费的大量时间，但它没有考虑整个问题下的情景，因此通过该算法得到的答案，不能确定是否为整个问题的最优解。也就是说，如果要使用贪心算法，应该在证明出通过贪心得出的答案就是最优解后再使用。
• 贪心算法一般只用于求最大或最小值。
• 贪心算法只能确定某些问题的可行性范围。

代码与应用

部分背包问题（P2240）

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N(N≤100)堆金币，第i堆金币的总重量和总价值分别是 m_i,v_i(1≤m_i,v_i≤100)。阿里巴巴有一个承重量为T(T≤1000)的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N,T。

接下来N行，每行两个整数 m_i,v_i。

输出格式

一个实数表示答案，输出两位小数。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=110;
 4 int n,t;
 5 struct node{
 6     int m;
 7     int v;
 8 };
 9 node a[N];
10 bool operator <(node a,node b){
11     return a.v*b.m>b.v*a.m;
12     /*用金币价值与金币质量的比值来比较不同金币的实际价值
14     return a.v*b.m>b.v*a.m的效果等同于return a.v/a.m>b.v/b.w，但由于在C++中“/”意为整除，所以需要使用其他方法代替除法*/
15 }
16 int main(){
17     scanf("%d%d",&n,&t);
18     for(int i=1;i<=n;++i)
19     {
20         scanf("%d%d",&a[i].m,&a[i].v);
21     }
22     sort(a+1,a+1+n);//重定义的的“<”会在这里用到
23     double ans=0;
24     for(int i=1;i<=n;++i)
25     {
26         if(a[i].m<=t)//当金币质量小于背包能容纳的剩余质量时，将这堆金币全部放进去
27         {
28             ans+=a[i].v;
29             t-=a[i].m;
30         }else{//当金币质量大于背包能容纳的剩余质量时，用这种金币将背包的剩余部分填满并结束循环
31             ans+=1.0*t*a[i].v/a[i].m;
32             break;
33         }
34     }
35     printf("%.2lf",ans);
36     return 0;
37 }