最少硬币问题

贪心算法

#include<bits/stdc++.h>
using namespace std;
const int n = 3;
int coin[] = {1,2,5};
int main(){
    int i, money;
    int ans[n] = {0};                          //记录每种硬币的数量
    cin >> money;                              //输入钱数
    for(i= n-1; i>=0; i--){                    //求每种硬币的数量
        ans[i] = money/coin[i];
        money = money - ans[i]*coin[i];
    }
    for(i= n-1; i>=0; i--)
        cout << coin[i]<<": "<<ans[i]<<endl;   //输出每种面值硬币的数量
    return 0;
}

笔记：贪心算法编程比较简单，也不会回头再看全局，是局部最优解，但不一定是全局最优解，但是如果问题满足拟阵结构，就可以获得最优解

拟阵伪代码

Greedy(S,L,w)           //拟阵M = (S,L)与权值函数 w
  A={}                  //A初始化为空集
  sort S by w           //将 s内的元素x按权值 w(x)从大到小降序排序
  for x in S:           //按 w(x)从大到小的顺序,遍历每个x∈S
    if (A ∪ {x} ∈ L)  //判断A和{x}的并集是否属于L（ S 的部分子集）
      A = A ∪ {x}      
  retuen A;             //返回权值最大独立集

笔记：一个问题能构造成拟阵一定可以用贪心算法，但是能用贪心算法不一定能使用拟阵构造