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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。