[Codeforces 10E] Greedy Change

Brief Introduction:

给你一些种类的硬币，用最少的硬币数表示X

求最小的使贪心算法错误的X

 

Algorithm:

一道论文题，《A Polynomial-time Algorithm for the Change-making Problem》

证明先挖个坑，以后再填

感性猜想，我们可以构建出这样一个算法：

对于一种币值A，我们找出一个略大于A仅用币值不小于B且小于A的货币表示的值X，使得贪心算法在使用A后要用更多零碎的货币

这样，只要枚举A、B，找出最小的这样的值即可。存在性问题论文中也有证明。

 

Code:

#include <bits/stdc++.h>using namespace std;int n,dat[500],res=-1;int main() {cin >> n;for(int i=1;i<=n;i++) cin >> dat[i];for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int cnt1=1,cnt2=0,W=dat[i]-1,t;for(int k=i+1;k<=j;k++) //非贪心做法cnt1+=(W/dat[k]),W%=dat[k];t=W=dat[i]-1-W+dat[j];for(int k=1;k<=n;k++) //贪心做法cnt2+=(W/dat[k]),W%=dat[k];if(cnt1<cnt2 && (res==-1 || res>t)) res=t;}cout << res;return 0; }

 

Review:

多看结论题

 

转载于:https://www.cnblogs.com/newera/p/9019000.html

总结

以上是生活随笔为你收集整理的[Codeforces 10E] Greedy Change的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。