poj1741，poj 3040 Allowance （貪心

     作為創紀錄的牛奶生產的獎勵，農場主約翰決定開始給Bessie奶牛一個小的每周津貼。FJ有一套硬幣N種（1≤N≤20）不同的面額，每枚硬幣是所有比他小的硬幣面值的倍數，例如1美分硬幣、5美分硬幣、10美分硬幣和50美分硬幣。使用這些硬幣，FJ每周至少給Bessie C（1 <= C <=100000000）美分。請你計算他最多能給Bessie幾周 
Input* 第一行N 、 C* 第 2..N+1行: 硬幣價值 V (1 <= V <= 100,000,000) 和數量 B (1 <= B <= 1,000,000) 
Output* 使用這些硬幣，每周至少給C美分的前提下的最多周數 
Sample Input3 610 11 1005 120Sample Output111

此題貪心情況有三個：

1.?對于硬幣面值大于c的，貪心情況是不搭配別的一次只發一個損失最小，先把這些發完

2. 對于可以湊成c的硬幣搭配，參與組合的硬幣面值越大，所用的硬幣越少，剩下的硬幣搭配的可能性更多，先把這些發完

3.?對于1.2情況處理后，用處理2的思路找出最接近c的硬幣搭配，再從小到大找最后一枚硬幣（已用2的思路貪心處理過了，結果已盡可能接近c而不到c，最后一枚參與的硬幣越小，損失約越小）

?

poj1741。注意2.3貪心情況的實現，湊c的循環可共同利用

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
struct node{int x,n;int m,mn;bool operator < (const node &rsh) const{return x<rsh.x;}
}a[30];
int main(){int n,c,ans=0;scanf("%d%d",&n,&c);for(int i=0 ; i<n ; i++)scanf("%d%d",&a[i].x,&a[i].n),a[i].m=0;sort(a,a+n);for(int i=n-1 ; i>=0 ; i--){                     //大于c的硬幣if(a[i].x>=c&&a[i].n>0)ans+=a[i].n,a[i].n=0;}int flag=1;while(flag){int mm=c,mn=inf;for(int i=n-1 ; i>=0 ; i--){                 //從大到小盡力填充a[i].m=0;if(a[i].n){a[i].m=min(a[i].n,mm/a[i].x);mm-=a[i].m*a[i].x;}if(mm==0)break;}if(mm>0){                                             //填充不了正好c，但此時就算是最小的硬幣也盡力填充了，決定是否大于c的只是最后的  一 枚硬幣for(int i=0 ; i<n ; i++){                  //用面值最小的硬筆開始填充，損失最小的貪心選擇if(a[i].x>mm&&(a[i].n-a[i].m)){a[i].m++;mm-=a[i].x;break;}}}if(mm>0)break;for(int i=0 ; i<n ; i++)if(a[i].m)mn=min(mn,a[i].n/a[i].m);ans+=mn;for(int i=0 ; i<n ; i++)if(a[i].m)a[i].n-=mn*a[i].m;}//for(int i=0 ; i<n ; i++)printf("%d %d\n",a[i].x,a[i].n);printf("%d",ans);return 0;
}

?