首页 > 代码库 > CF10E Greedy Change 判断硬币系统是否能用贪心策略
CF10E Greedy Change 判断硬币系统是否能用贪心策略
Billy investigates the question of applying greedy algorithm to different spheres of life. At the moment he is studying the application of greedy algorithm to the problem about change. There is an amount of n coins of different face values, and the coins of each value are not limited in number. The task is to collect the sum x with the minimum amount of coins. Greedy algorithm with each its step takes the coin of the highest face value, not exceeding x. Obviously, if among the coins‘ face values exists the face value 1, any sum x can be collected with the help of greedy algorithm. However, greedy algorithm does not always give the optimal representation of the sum, i.e. the representation with the minimum amount of coins. For example, if there are face values {1, 3, 4} and it is asked to collect the sum 6, greedy algorithm will represent the sum as 4 + 1 + 1, while the optimal representation is 3 + 3, containing one coin less. By the given set of face values find out if there exist such a sum x that greedy algorithm will collect in a non-optimal way. If such a sum exists, find out the smallest of these sums.
Input
The first line contains an integer n (1 ≤ n ≤ 400) — the amount of the coins‘ face values. The second line contains n integers ai (1 ≤ ai ≤ 109), describing the face values. It is guaranteed that a1 > a2 > ... > an and an = 1.
Output
If greedy algorithm collects any sum in an optimal way, output -1. Otherwise output the smallest sum that greedy algorithm collects in a non-optimal way.
Sample test(s)
input
5
25 10 5 2 1
output
-1
input
3
4 3 1
output
6
参考论文《A polynomial-time algorithm for the change-making problem》
设找零钱的最小表示为M(x),贪心表示为G(x),最小不满足M(x)=G(x)的值为w。
如题中input2,M(6)={0,2,0}, G(6)={1,0,2}。
设M(w)第一个非0元素在位置i,最后一个非0元素在位置j
有这么一个结论:
M(w)和G(c[i-1]-1)从1到j-1位都相等,M[j]=G[j]+1。
于是可以通过枚举i,j求出w的值。
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <stack> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstring>10 #include <iostream>11 #include <algorithm>12 #define ll long long13 #define pii pair<int, int>14 #define mp(x,y) make_pair(x,y)15 using namespace std;16 const int inf = 0x7fffffff;17 const double eps = 1e-12;18 const int mod = 1e9+7;19 const int maxn = 300005;20 using namespace std;21 int c[401];22 int main() {23 int n;24 cin>>n;25 for (int i=0; i<n; i++)26 cin>>c[i];27 int ans=-1;28 for (int i=1; i<n; i++) {29 for (int j=i; j<n; j++) {30 //calculate G(c[i-1]-1) and w31 int p=c[i-1]-1, cnt=1, w=c[j];32 for (int k=i; k<=j; k++) {33 cnt+=p/c[k];34 w+=p/c[k]*c[k];35 p%=c[k];36 }37 p=w;38 //judge whether M(w)<G(w)39 for (int k=0; k<n; k++) {40 cnt-=p/c[k];41 p%=c[k];42 }43 if (cnt<0&&(ans==-1||w<ans))44 ans=w;45 }46 }47 cout << ans << endl;48 return 0;49 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。