Codeforces 10E Greedy Change
Published:
题目
https://codeforces.com/contest/10/problem/E
一个整数硬币系统，满足c[1] > c[2] > … > c[n]，且c[n] = 1。
对于钱数w，为了用最少的硬币数表示出w，有一种贪心算法：不断地取<=w的最大的c[i]，然后w-=c[i]。例如人民币来说，128就可以表示成100 + 20 + 5 + 1 + 1 + 1，共6张钱，也是最优的。
显然这种贪心算法不一定总能得到最优解。例如货币系统4,3,1，当钱数w=6时，贪心算法会得到4+1+1共3个硬币，但最优解是3+3共2个硬币。
现在给定c[1..n]，问这个硬币系统会不会出现贪心算法得不到最优解的问题。如果会出现，那么求出最小的w，使得贪心算法失效。n<=400，0<=c[i]<=10^9。
题解
这道题就是论文《A Polynomial-time Algorithm for the Change-Making Problem》讨论的问题。下载：https://drive.google.com/file/d/1u8fMFGA4myi2ZgJL3TDoNGe6EHH1w16e/view?usp=sharing
以下内容基本是翻译论文内容。
首先，给定c[1..n]和 $w$，要得到 $w$ 的最优解，是NP-Hard的。要判断对 $w$ 来说，贪心算法是否是最优解，也是NP-Hard的（虽然这个问题比上面的问题简单一些）。
但是，判断是否存在某个 $w$ 使得贪心算法失效，以及求出这个最小的 $w$，却有 $O(n^3)$ 的多项式解法。这跟前面两个NP-Hard的问题并不矛盾。
| 首先定义硬币系统为 $C=(c_1,c_2,…,c_n)$ 是一个n维向量。定义一个组合为 $V=(v_1,v_2,…,v_n)$ ，那么 $w=V\cdot C=\sum_{i=1}^nv_ic_i$ 就是这个组合得到的钱数。定义 $ | V | =\sum_{i=1}^nv_i$ 。 |
| 对于$w$来说，设由贪心算法得到的组合为 $G(w)$，最佳组合为 $M(w)$。我们的问题就是，求最小的 $w$，使得 $ | G(w) | > | M(w) | $。如果有多个最佳组合，$M(w)$ 为字典序最大的那个。 |
定义两个$n$维向量的小于关系：$U<V$，代表$U$的字典序小于 $V$。定义包含关系 $U\subset V$，表示对任意 $i$，都有 $u_i\le v_i$。
我们可以证明几个性质：
- 如果 $a\lt b$ ，那么字典序 $G(a)\lt G(b)$ 。但对于$M$不具备此性质。
- 对于任意可以表示出$w$的组合$V$，都有 $V\le G(w)$ 。也就是说，贪心算法得到的是字典序最大的$V$。
- 如果$U\subset V$，且 $V=G(V\cdot C)$ ，那么 $U=G(U\cdot C)$ 。根据贪心过程即可证明。
- 如果$U\subset V$，且 $V=M(V\cdot C)$ ，那么 $U=M(U\cdot C)$ 。根据最佳组合的定义即可证明。
| **假设 $w$ 是最小的满足 $ | G(w) | > | M(w) | $ 的钱数**。我们可以发现，$G(w)$ 和 $M(w)$ 一定是不相交的，也就是说如果某个位置 $i$ 上某一个大于 $0$，那么另一个在位置 $i$ 上一定等于 $0$。这是因为我们找的是最小的 $w$。如果某个位置 $i$ 上 $G(w)$ 和 $M(w)$ 都大于 $0$，那么 $w-c_i$ 就成了一个更小的满足条件的值。 |
同时字典序 $M(w)<G(w)$。假设 $M(w)$ 中第一个非0的位置是 $i$，最后一个非0的位置是 $j$，那么对于 $G(w)$ 而言，它在第 $i$ 位上必须是 $0$。因此 $G(w)$ 必定在 $1$ 到 $i-1$ 之间有非 $0$ 的值，才能保证字典序最大。这也告诉我们，$i>1$。
接下来我们证明Theorem 1：$M(w)$ 与 $G(c_{i-1}-1)$ 在 $1$ 到 $j-1$ 位都相同，在第 $j$ 位上比后者大 $1$，在第 $j+1$ 到 $n$ 位都等于0。
证明：
因为 $G(w)$ 在 $1..i-1$ 之间有非 $0$ 位置，所以 $w\ge c_{i-1}$。
考虑 $w-c_j$，因为 $w$ 是最小的贪心算法失效的钱数，那么必有 $M(w-c_j)=G(w-c_j)$。同时可以发现，$M(w-c_j)$ 与 $M(w)$ 只是在第 $j$ 位相差 $1$。因为，对于 $w-c_j$ 而言，贪心的时候第一个贪到的数是 $c_i$，因此 $w-c_j\lt c_{i-1}$
于是我们得到：$w-c_j\lt c_{i-1} \le w$
对于 $c_{i-1}-1$ 来说，第一个贪心到的数是 $c_i$。我们考虑将第 $i$ 位减去 $1$，得到 $c_{i-1}-1-c_i$，有 $c_{i-1}-1-c_i\lt w-c_i$，因此有 $G(c_{i-1}-1-c_i)<G(w-c_i)=M(w-c_i)$。那么我们在第 $i$ 位上加上 $1$，不会改变字典序大小，那么就得到 $G(c_{i-1}-1)<M(w)$。
另外因为 $c_i-1\ge w-c_j$，那么 $G(c_{i-1}-1)\ge G(w-c_j)=M(w-c_j)$。于是我们得到： \(M(w-c_j) \le G(c_{i-1}-1)<M(w)\)
这里的小于是字典序小于。注意到两头的两项只在第 $j$ 位差 $1$，并且第 $j$ 位是 $M(w)$ 的最后的非 $0$ 位置，因此 Theorem 1 得证。
那么如何找到最小的 $w$ 呢？ $O(n^2)$ 枚举 $i$ 和 $j$，求出 $G(c_{i-1}-1)$，然后就可以求出 $w$，然后再判断一下 $w$ 是否满足条件即可。总复杂度 $O(n^3)$。
代码
https://codeforces.com/contest/10/submission/149007309
思考
问题来了，如果我没看过这篇论文咋整？好像也没啥办法，能想出来的最多也就限于Theorem 1之前的那部分了。可能通过一些打表观察来找到 $c_{i-1}-1$ 的规律吧。