概念：
当一个问题具有最优子结构性质时，可用动态规划算法，有时会有更简单有效的算法，那就是贪心算法，贪心算法是通过一系列的选择来得到问题的解，贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优解。但对范围相当广的许多问题能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。
贪心算法的基本要素：
贪心选择性质：所求解的问题的整体最优解可以通过一系列局部最优的选择来，即贪心选择达到。贪心选择所依赖的是以前所做过的选择，而对以后所做的选择没有关系。
最优子结构性质：一个问题的最优解包含其子问题的最优解。
贪心算法与动态规划的区别：
动态规划是通过自底向上的方式解决子问题，贪心算法是通过自顶向下的迭代方式做出贪心选择，求解问题的最优解。两共同点是都具有最优子结构性质。
1.欢聚时代：容量M,电影N部，每部喜爱值不一样，电影大小不一样，求不超过容量最喜欢的值
100 5//容量，5部电影
29 28 19 18 20//电影容量
9 4 3 8 10//每部喜爱值
#include <iostream> #include <map> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { int cap,num,tmp; map<int, int, greater<int>> love_size; cin >> cap>>num; cout << cap << ":" << num << endl; vector<int> movie, love; for (int i = 0; i < num;i++) { cin >> tmp; movie.push_back(tmp); } for (int i = 0; i < num; i++) { cin >> tmp; love.push_back(tmp); } for (int i = 0; i < num;i++) { love_size.insert(make_pair(love[i],movie[i])); } int love_sum=0; int movie_cap = 0; for (auto v:love_size) { movie_cap += v.second; love_sum += v.first; cout << "select:" << v.first << ":" << v.second <<":"<<love_sum<<endl; if (movie_cap >= cap) { if (movie_cap> cap) love_sum -= v.first; break; } } cout << love_sum << endl; system("pause"); }
华为：一百块钱需要买100只鸡，公鸡5元一只，母鸡3元一只，小鸡一元三只。请输出所有可能的情况。
5*x+3*y+z/3=100
x+y+z=100
0=<x<=25
0=<y<=33
0=<z/3<=100
#include<iostream.h> void main() { int x,y,z,count=0; cout<<"百钱买百鸡的方案有："<<endl; for(x=0;x<=20;x++) for(y=0;y<=33;y++) for(z=0;z<=300;z=z+3) if(5*x+3*y+z/3==100&&x+y+z==100) { ++count; cout<<count<<":"<<x<<","<<y<<","<<z<<endl; } }
类似的比如百度：
x+2*y=N;
0<=x<=N
0<=y<=N/2
原文：https://www.cnblogs.com/bwbfight/p/11505264.html