題目鏈接: poj 3040
貪心 看到題目的時候完全沒有什么思路，這類題目做的還是太少了，完全是面向題解編程。
我的（bierende）思路：第一時間肯定是想到浪費的越少越好。 1. 當幣值大于C的時候，就直接用這個硬幣付工資。 2. 當幣值小于C的時候，就要想一種搭配方案，使得總的價值等于或者多于C但多余的錢要盡可能少，這個就比較難想到了。
而題目中有一個條件是，大的幣值能被小的整除，所以若干個小的一定能湊出大的，那么可以用一個大的或若干個小的的情況下，肯定是要選用一個大的，這樣之后的搭配方案才能更好的符合”超出C的錢盡可能少“這個條件。
所以， 當當幣值小于C的時候，從幣值最大的開始遍歷，一個小于C，那兩個、三個一直到n個，直到剛好等于C或者n+1個硬幣大于C，如果是后者，那就選n個，在從幣值更小的硬幣重復上面的過程，直到剛好等于C或者全部硬幣遍歷完 如果最后的全部遍歷完還是不能湊到剛好等于C，那么從小到大，直到找到一個加上這個硬幣剛好大于C的。如果找不到，就說明剩下的全部加起來已經沒有C了，結束了
#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int MAXN = 25;pair<int,int> p[MAXN];//存儲硬幣幣值和數量int n, c;int main(){ while(scanf("%d%d", &n, &c) == 2) { for(int i=0; i<n; i++) scanf("%d%d", &p[i].first, &p[i].second); sort(p, p+n);//按幣值從小到大排序 int ans = 0, require, need[MAXN], rest; while(true) { rest = c; memset(need, 0, sizeof(need)); for(int i=n-1; i>=0; --i)//從大到小選擇 { if(p[i].second>0) { require = min(p[i].second, rest/p[i].first);//需要這個幣值的硬幣的數量 rest -= require*p[i].first; need[i] = require; } if(rest == 0) break;//剛好湊出C } if(rest) { for(int i=0; i<n; i++)//從小到大選擇 { if(p[i].second && p[i].first>=rest)//加上這個硬幣（最小）就剛好大于C { rest = 0; need[i]++; break; } } } if(rest) break;//兩輪選擇后仍然湊不齊C，結束 int week = 1e8;//用這個方案能發多少個星期的工資 for(int i=0; i<n; i++) { if(need[i]) week = min(week, p[i].second/need[i]); } ans+=week; for(int i=0; i<n; i++)//把用掉的硬幣減去 { if(need[i]) p[i].second -= week*need[i]; } } cout << ans << endl; } return 0;}新聞熱點
疑難解答
