leetcode(3):找零钱问题（贪心||动规）
文章目录
1. 贪心算法2. 贪心+回溯3. 动态规划方法3.1 动规分析3.2 状态压缩3.3 初始状态
找零钱问题——题目大意：
小明手上有零钱10元、5元、1元、5角、2角、1角若干，现需要找零57.8元，求出零钱数最少的组合方案
1. 贪心算法
贪心算法的由来和乌鸦喝水的故事差不多。简而言之，乌鸦喝水的时候呢，应该是先把大的石块丢进瓶子里，再把小的丢进瓶子里； 在这里就是先用大的，依次用小的；
一般情况下贪心算法就可以解决找零钱问题，而且代码比较简单，代码如下
#include
using namespace std;
int main()
{
float total=0.0;
cin>>total;
float sum=total;
const float a[]={10,5,1,0.5,0.2,0.1};
int i,b[6]={0};
for(i=0;i<6;++i)
{
b[i]=total/a[i];
total=total-b[i]*a[i];
//浮点数最后一个可能存在问题，int直接删掉if
if(i==5 && total > 0)
{ b[5]++;
}
}
for( i=0;i<6;i++)
{
cout< } system("pause"); return 0; } 2. 贪心+回溯 如果找零钱的问题，稍微升级一下： 此时简单的贪心算法就会出问题了； 该题就可以用：贪心+回溯 贪心：首先选择面值较大的零钱。 回溯：若某个大零钱选择之后，它后面的小零钱不能完成兑换的话，需要回溯，也就是将面值较大的零钱减少一张。 加速 ：每次直接将面值大的零钱选用最大张数，加速零钱兑换； 剪枝：若可兑换的零钱数大于 res 了，那么我们应该剪枝，也就是将将面值较大的零钱减少一张。 3. 动态规划方法 3.1 动规分析 /**动态规划模型构造 * 对于4个城市的情况 城市的邻接矩阵如下： S0 S1 S2 S3 S0 0 3 6 7 S1 5 0 2 7 S2 6 6 0 2 S3 3 3 5 0 */ 动规肯定会涉及到 状态转移方程、和最优子问题，最重要的需要明确 状态的Base和Case； 例如大问题是从顶点0开始，经过顶点1，2，3然后回到顶点1的最短路程，那么我们可以分割为三个小问题找最优解： 从顶点0出发到顶点1，再从顶点1出发，途径2，3城市（不保证访问顺序），然后回到0的最短路径。从顶点0出发到顶点2，再从顶点2出发，途径1，3城市，然后回到0的最短路径从顶点0出发到顶点3，再从顶点3出发，途径1，2城市，然后回到0的最短路径 /* 假设找出的一条最短的回路：S0-S1-S2 -S3-S0 我们可以利用结论： "S1 S2 S3 S0 "必然是从S1到S0通过其它各点的一条最短路径(如果不是，则会出现矛盾) Length(总回路) = Length(S0，S1) + Length(S1,S2,S3,S0) Length(回路) =Min{ Length(0,1)+Length(1,…,0), Length(0,2)+Length(2,…,0), Length(0,3)+Length(3,…,0)} */ 上面小问题可以看出: 动规至少需要一个二维dp数组，来进行递归。 规范表达上面公式： 注意:经过的路线是一条经过所有城市的闭合回路, 因此从哪一点出发是无所谓的, 因此不妨设从城市0出发。 V是一个集合； d(i，V) ：表示从i点经过点集Ｖ各点一次之后回到出发点的最短距离 d(i，V’) ＝ min {Cik+d(k,V－{k})} (k∈V’) d(k，{ }) ＝ Cik (k≠i) 其中，Cik表示i到k的距离 因此从城市0出发，经城市1，2，3然后回到城市0的最短路径长度是： d(0, {1, 2, 3})=min{C01+ d(1, { 2, 3}), C02+ d(2, {1, 3}),C03+ d(3, {1, 2})} 这是最后一个阶段的决策，它必须依据d(1, { 2, 3})、 d(2, {1, 3})和d(3, {1, 2})的计算结果,而： d(1, {2, 3})=min{C12+d(2, {3}), C13+ d(3, {2})} d(2, {1, 3})=min{C21+d(1, {3}), C23+ d(3, {1})} d(3, {1, 2})=min{C31+d(1, {2}), C32+ d(2, {1})} 继续写下去： d(1, {2})= C12+d(2, {}) d(2, {3})=C23+d(3, {}) d(3, {2})= C32+d(2, {}) d(1, {3})= C13+d(3, {}) d(2, {1})=C21+d(1, {}) d(3, {1})= C31+d(1, {}) dp表 下面就涉及到如何表示点集V的问题了； 3.2 状态压缩 本节主要参考文章:传送门 状态压缩就是：用数组的下标索引当成一个位图，用其中的 每个bit位代表已经经过哪些城市 规定：从1到n-1（n为城市的个数）用二进制表示的话，刚好可以映射成除了0号城市外的剩余n-1个城市在不在子集n[j]，1代表在，0代表不在 例：若有总共有4个城市的话，除了第0号城市，对于1-3号城市 111 = V-1 = 2^3 - 1 = 7 ，从高位到低位表示3到1号城市都在子集中 而101 = 5 ，表示3,1号城市在子集中，而其他城市不在子集中 所以dp数组的宽度为城市的数量 ；该索引的大小为：1 << n（n为城市的个数） 3.3 初始状态 下一步就是开始定C++语言的数据结构和dp数组的初始状态； 数据结构用vector int Hvol = 1 << G.size();