贪心算法总结_贪心算法的概念总结

小知识点

1、定义比较函数

struct f;
bool cmp(f a,f b)
{
    
if(a.x!=b.x) return a.x<b.x;
  else return a.y<b.y;
  }
1
2
3
4
5
6
7

2、重载运算符

struct A
{
   int a,b;
bool operator < (const A)const
{
   
return b<=A.x;
}
1
2
3
4
5
6
7
8

3、pair

pair <int ,int> p;
p.first=  ;
p.second=    ;
1
2
3

可以存储两个元素，想坐标一样的东西
4、substr操作 a.substr(起始位置，结束位置)；

例题思路与代码

1、背包问题 可分割
思路 按照性价比由大到小存放，当背包空间不够时，剩余空间可以存放分割后的，注意性价比一块定义在结构体中，double定义性价比

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iomanip>
using namespace std;
struct bag
{
   
    int r;
    int   v;
    double  p;
};
bool cmp(bag x,bag y)
{
   
    return x.p>y.p;
}
int main()
{
   
   int k,w,n;
   bag a[10001];
   cin>>k;
   while(k--)
   {
   
       memset(a,0,sizeof(a));
       cin>>w>>n;
        int zw=0;
       double V=0.0;
       for(int i=1;i<=n;i++)
       {
   
           cin>>a[i].r>>a[i].v;
           a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35