POJ1276Cash Machine

http://poj.org/problem?id=1276

题意 ： 给你一个目标钱数，再给你钱币的种数和钱币的面值，让你用这些钱凑出不大于目标钱数的钱然后输出这个最接近且不大于目标钱数的钱。

思路 ： 背包问题，还是多重背包，就是找到公式然后注意一下数组大小，还要小小的注意一下，因为那个钱数的范围挺大的，做一个小小的优化吧也算是 。

代码 ： 

#include
#include
#include
using namespace std ;
struct node
{int n;int d ;
} cas[21] ;
int main()
{int cash ;int n,ch[110000] ;while(scanf("%d",&cash)!=EOF){int m;cin>>n ;for(int i = 0 ; i < n ; i++)cin>>cas[i].n >>cas[i].d ;memset(ch,0,sizeof(ch)) ;ch[0] = 1 ;/*ch是标记数组，也可以说是一个小小的优化吧，再已经标记的基础上继续往上加，不用再从头开始加了,否则会超时*/int maxm = 0 ;//for循环从每种纸币开始，再对钱数进行枚举，每种纸币又有n张for(int i = 0 ; i < n ; i++)for(int j = maxm ; j >= 0 ; j--)if(ch[j])for(int k = 1 ; k <= cas[i].n ; k++){m = j + cas[i].d * k;if(m > cash)break ;ch[m] = 1 ;if(m > maxm)maxm = m ;}cout<endl ;}return 0 ;
}