贪心策略：总是考虑在当前状态下局部最优的策略，一定满足最优子结构，不断地把问题归纳为更小的相似地子问题
拟阵：许多用贪心算法求解的问题，可以表示求带权拟阵的最大权独立子集问题
最少硬币问题：
给定面值，给定要付的钱，求最少需要多少硬币
！如果面值为1、2、5或者1、2、4、8这种才可以用贪心计算，只有面值任一硬币面值都大于比它小的的和，才能计算
//先排序
int mon[10]={1,2,5};
int all;
cin>>all;
int num[10];
for(int i=0;i<3;i++){
num[i]=all/mon[i];
all=all-mon[i]*num[i];
}
对于任意面值的求解：动态规划
1、打印最少硬币组合
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
int money=251;
int tot=5;
int type[5]={1,5,10,25,50};
int num[maxn];
int path[maxn];
void prin(int *path,int s){
while(s){
cout<<path[s]<<" ";
s-=path[s];
}
}
void sovle(){
for(int i=0;i<money;i++) num[i]=INF;
num[0]=0;
for(int j=0;j<tot;j++){
for(int i=type[j];i<money;i++){
if(num[i]>num[i-type[j]]+1){
num[i]=num[i-type[j]]+1;
path[i]=type[j];
}
}
}
}
int main(){
int s;
sovle();
while(cin>>s){
cout<<num[s]<<endl;
prin(path,s);
}
return 0;
}
2、每种硬币有数量限制
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//所有硬币组合，而且对硬币的数量有限制
int a[5]={1,5,10,25,50};
int dp[251][110];
int n;
//先打表
void sovle(){
dp[0][0]=1;
for(int i=0;i<5;i++){
for(int j=1;j<101;j++){
for(int k=a[i];k<251;k++)
dp[k][j]+=dp[k-a[i]][j-1];
}
}
}
int ans[251]={0};
int main(){
sovle();
for(int i=0;i<251;i++){
for(int j=0;j<101;j++) ans[i]+=dp[i][j]; //从0开始，因为dp[0][0]=1
}
while(cin>>n){
cout<<ans[n]<<endl;
}
return 0;
}
区间贪心：
一、区间不相交问题
总是选择左端点最大的区间
struct node{
int x,y;
}a[maxn];
bool cmp(node a,node b){
if(a.x!=b.x) return a.x>b.x; //先按照左端点从大到小排序
else return a.y<b.y; //不然就是右端点从小到大
}
sort(a,a+n,cmp);
int ans=1,lastx=a[0].x;
for(int i=1;i<n;i++){
if(a[i].y<=lastx){
ans++;
lastx=a[i].x;
}
}
二、区间选点问题
最少确定多少个点，才能使每个闭区间都至少存在一个点，和区间不相交问题一样，只需要改成a[i].y<lastx就可以了
最小生成树算法：常用的是prim和kruskal算法，都是采用了贪心的思想，但是策略不一样。
三、活动安排问题
按照结束时间排序
struct node{
int st,ed;
}ac[maxn];
bool cmp(node a,node b){
return a.ed<b.ed;
}
void solve(){
int n;cin>>n;
for(int i=0;i<n;i++) cin>>ac[i].st>>ac[i].ed;
sort(ac,ac+n,cmp);
int ans=0;
int lastend=-1;
for(int i=0;i<n;i++){
if(ac[i].st>=lastend){
ans++;
lastedn=ac[i].ed;
}
}
return ans;
}
四、区间覆盖问题
给出线段的左右端点，求最少要多少线段覆盖整个区间
先按照左端点排序，然后在剩下的里面选择左端点在R且右端点最大的
五、最优装载问题
六、多机调度问题
最长处理时间优先
背包问题
一、部分背包问题：可以选择拿一件物品地部分东西，这个完全可以用贪心，选择当前单位价值最大的
二、01背包问题：因为要和选和不选的两种情况比较，所以产生的子问题互为重叠，需要用动态规划