NYOJ995硬币找零(简单dp)

/*

 题意：给你不同面额的硬币（每种硬币无限多），需要找零的面值是T，用这些硬币进行找零，

 如果T恰好能被找零，输出最少需要的硬币的数目！否则请输出剩下钱数最少的找零方案中的最少硬币数！

 思路：转换成完全背包的问题！ 

#include iostream 

#include cstring 

#include cstdio 

#include algorithm 

#define INF 0x3f3f3f3f

using namespace std;

int dp[100005];

int main(){

 int n, v;

 while(cin n v (n||v)){

 memset(dp, 0x3f, sizeof(dp));

 dp[0]=0;//不要忘记这一步 

 for(int i=1; i ++i){

 int k;

 cin k;

 for(int j=k; j ++j)

 dp[j]=min(dp[j], dp[j-k]+1);//这里是min，不是max 

 for(int i=v; i --i)//如果遇到了找零的数目不是INF,那么就是答案！ 

 if(dp[i]!=INF){

 dp[v]=dp[i];

 break;

 cout dp[v] endl;

 return 0;

}