1 /* 2     题意：给你不同面额的硬币（每种硬币无限多），需要找零的面值是T，用这些硬币进行找零， 3     如果T恰好能被找零，输出最少需要的硬币的数目！否则请输出剩下钱数最少的找零方案中的最少硬币数！ 4      5     思路：转换成完全背包的问题！  6 */ 7 #include<iostream> 8 #include<cstring> 9 #include<cstdio>10 #include<algorithm>11 #define INF 0x3f3f3f3f12 using namespace std;13 int dp[100005];14 15 int main(){16     int n, v;17     while(cin>>n>>v && (n||v)){18         memset(dp, 0x3f, sizeof(dp));19         dp[0]=0;//不要忘记这一步 20         for(int i=1; i<=n; ++i){21             int k;22             cin>>k;23             for(int j=k; j<=v; ++j)24                dp[j]=min(dp[j], dp[j-k]+1);//这里是min，不是max 25         }26         for(int i=v; i>=0; --i)//如果遇到了找零的数目不是INF,那么就是答案！ 27               if(dp[i]!=INF){28                    dp[v]=dp[i];29                  break;30               }31         cout<<dp[v]<<endl;32     } 33     return 0;34 }