RMB找零问题

来自某次研究性学习的作业

前言

可以先考虑这样的问题

给定 \(n\) 种足量多的纸币，每种面额为 \(a_i\) 元 \((0<a[i]≤10000,a[i]\in \mathbb{Z},1\le i\le n\le 100)\)

给出需要找零的金额 \(m (0≤m≤10000)\)

请找到一种方法使得找零所需的纸币数量尽可能地少，输出最小数量

例如：\(68=50+10+5+2+1,12=10+2\)

尽管 \(8=10-2\) ，但是收银员是不能支付 \(-2\) 元的

可以看出这就是一道完全背包模板题

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[105],dp[100005];
signed main()
{
	ios::sync_with_stdio(0);
	cin >> n >> m;
	memset(dp,0x3f,sizeof(dp));dp[0]=0;
	for(int i=1; i<=n; i++)
		cin >> a[i];
	for(int i=1; i<=n; i++)dp[a[i]]=1;
	for(int i=1; i<=n; i++)
		for(int j=a[i]; j<=m; j++)
			dp[j]=min(dp[j],dp[j-a[i]]+1);
	cout << dp[m] << endl;
	return 0;
}

而本文讨论的是关于RMB（人民币）的找零问题

---

特殊的找零问题

考虑这样的问题

给定足量多的纸币，面额为 \(1,2,5,10,20,50,100\) 元

给出需要找零的金额 \(m(0≤m≤10^9)\)

请找到一种方法使得找零所需的纸币数量尽可能地少，输出最小数量

例如：\(68=50+10+5+2+1,12=10+2\)

尽管 \(8=10-2\) ，但是收银员是不能支付 \(-2\) 元的

根据生活常识，我们可以发现这其实是个贪心问题

那我们来尝试证明

先把概念放一下

首先能用贪心解决的问题需要具备贪心选择和最优子结构的性质

---

贪心选择

所谓贪心选择是指应用同一规则，将原问题转变成一个相似的但规模更小的子问题，而后的每一步 都是当前看似最佳的选择，且这种选择只依赖于已做出的选择，不依赖于未做出的选择

也就是说所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划的主要区别。

在动态规划中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。

而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解出做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划通常以自底向上的方式解各个问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题

---

最优子结构

执行算法时，每一次得到的结果虽然都是当前问题的最优解（即局部最优解），但只有满足全局最

优解包含局部最优解时，才能保证最终得到的结果是最优解

---

证明

设 \(c_i\) 为第 \(i\) 种纸币的面额， \(S_i\) 为总金额为 \(i\) 时的最小花费

设总金额为 \(n\) ，则原问题的最优解即为 \(S_n=k\)

现在将某一面值的纸币 \(c_j\) 减少 \(1\) ，则有 \(S_{n-c_j} = k-1\) 为总金额 \(n-c_j\) 时的最优解

否则设 \(T_{n-c_j} = m\) 为总金额 \(n-c_j\) 时的最优解，即 \(m<k-1\)

则 \(T_{n-c_j} + 1\) 应为原问题的最优解，即 \(m+1<k-1+1=k\) ，与最小花费为 \(k\) 相矛盾

又由于纸币的数量足够多，因此问题间相互独立

故问题满足最优子结构性质

设 \(c_i\) 为第 \(i\) 种纸币的面额，\(x_i\) 为贪心得到的最优解 \(\sum x_i\) 中使用第 \(i\) 种纸币的数量，

\(y_i\) 为原问题最优解 \(\sum y_i\) 中使用第 \(i\) 种纸币的数量，令 \(x_i<x_{i+1},y_i<y_{i+1}\)

假设贪心的得到的最优解不是原问题的最优解，则存在一个最大的 \(k\) ，使得 \(x_k\ne y_k\)

可以发现 \(k\ne 1\)

情况1：若 \(x_k<y_k\) ，由于贪心算法每次选择的都是最大面额的纸币，因此不存在

情况2：若 \(x_k>y_k\) ，此时一定使用了较小面额的纸币来替代 \(c_k\) ，即 \(\sum{c_i}=c_k\)

显然对于任意一个币值，任意 \(2\) 张小于它的相加都小于它，例如 \(1+2<5\)

因此此时 \(\sum x_k < \sum y_k\) ，与 \(\sum y_k\) 是最优解相矛盾，因此不成立

故问题满足贪心选择性质

因此我们就可以 \(O(1)\) 求解了

代码不放了比较简单

---

其他情况

可以猜测，可能存在其他的情况也满足贪心的性质

还没研究 qwq 但是找到了一篇论文

https://arxiv.org/pdf/0809.0400v1.pdf

是关于怎样的面额才能使用贪心算法的

---

总结

简单证明了一下某些特定找零问题贪心算法的正确性

---

参考文献

[1] 人民币找零的贪婪算法最有解的证明