贪心算法
每一步都力求最大限度地解决问题，每一步都选择的是当前最优的解决方案，这种解决问题的算法就是贪心算法。
举例：
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？
#include <iostream>
#include <math.h>
using namespace std;
//当前的钱库，面值以及对应数量
int single_money[7] = {1,2,5,10,20,50,100};
int number_money[7] = {2,5,0,3,4,0,4};
//每种面值使用贪心算法后需要使用的张数
int count[7] = {};
int total_count;
int tanxin(int money)
{
if (money >= 0) //考虑一下输入规范的问题
{
for (int i = 6; i >= 0; i--)
{
count[i] = min(number_money[i],money/single_money[i]);
money = money - count[i]*single_money[i];
}
return 0;
}
else
{
return money;
}
}
int main(int argc,char** argv)
{
int money;
cout<<"Please input the amount of money:";
cin>>money;
if(! tanxin(money))
{
cout<<"贪心最优结果为："<<endl;
cout<<"100元："<<count[6]<<"张"<<endl;
cout<<"50元："<<count[5]<<"张"<<endl;
cout<<"20元："<<count[4]<<"张"<<endl;
cout<<"10元："<<count[3]<<"张"<<endl;
cout<<"5元："<<count[2]<<"张"<<endl;
cout<<"2元："<<count[1]<<"张"<<endl;
cout<<"1元："<<count[0]<<"张"<<endl;
}
else
{
cout<<"Ops, Wrong number~";
}
return 0;
}贪心算法注重的是每一步选择最优的解决方案（又称“局部最优解”），并不关心整个解决方案是否最优。
贪心算法常用来解决部分背包问题。
在限定条件下，如何从众多物品中选出收益最高的几件物品，这样的问题就称为背包问题
根据不同的限定条件，背包问题还可以有更细致的划分：
- 0-1 背包问题：每件物品都不可再分，要么整个装入背包，要么放弃，不允许出现类似“将物品的 1/3 装入背包”的情况；
- 部分背包问题：每件物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；
- 完全背包问题：挑选物品时，每件物品可以选择多个，也就是说不限物品的数量。
- 多重背包问题：每件物品的数量是有严格规定的，比如物品 A 有 2 件，物品 B 有 3 件。
贪心算法和动态规划算法
💡 贪心选择性质是贪心算法与动态规划算法的主要区别：
- 在动态规划算法中，每步所做的选择依赖于相关子问题的解，所以只有解决相关子问题后，才能做出选择。
- 而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，再去解做出这个选择后产生的相应的子问题。也就是说，贪心算法所做的贪心选择可以依赖过去所做过的选择，但绝不依赖将来所作的选择，也不依赖子问题的解。
⭐ 正是由于这种差别，动态规划算法是自底向上的，而贪心算法是自顶向下的，以迭代的方式做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为规模更小的子问题。
区间调度问题
【题目】给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。
int intervalSchedule(int[][] intvs) {}举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
【解题思路】正确的思路其实很简单，可以分为以下三步：
- 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
- 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
- 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
#include<iostream>
using namespace std;
int intervals[][2]={{1,3},{3,6},{2,4}};
void sort(){
for(int i=0;i<3;i++){
int temp[][1]={0};
if (intervals[i][1]>intervals[i+1][1]){
temp[0][0] = intervals[i][0];
temp[0][1] = intervals[i][1];
intervals[i][0] = intervals[i+1][0];
intervals[i][1] = intervals[i+1][1];
intervals[i+1][0] = temp[0][0] ;
intervals[i+1][1] = temp[0][1] ;
}
}
}
int main(){
sort(); //先给区间升序排列
int count = 0; // 最大的不相交区间的数量
int x_end = intervals[0][1]; // 从最小的 end 开始
for(int i=1;i<3;i++){
int start = intervals[i][0];
int end = intervals[0][i];
if(start >= x_end){
count ++;
x_end = end;
}
}
cout<<count<<endl;
return 0;
}本文引用来源：
