1 /* 2 題意：給你不同面額的硬幣（每種硬幣無限多），需要找零的面值是T，用這些硬幣進行找零， 3 如果T恰好能被找零，輸出最少需要的硬幣的數目！否則請輸出剩下錢數最少的找零方案中的最少硬幣數！ 4 5 思路：轉換成完全背包的問題！ 6 */ 7 #include<iostream> 8 #include<cstring> 9 #include<cstdio> 10 #include<algorithm> 11 #define INF 0x3f3f3f3f 12 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 }
?
)
)
)
