首页 > 代码库 > UVa 674 Coin Change(完全背包)

UVa 674 Coin Change(完全背包)

https://vjudge.net/problem/UVA-674

题意:

计算兑换零钱的方法共有几种。

 

思路:

完全背包基础题。

 1 #include<iostream>  2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6  7 int d[7500]; 8 int a[5] = { 1, 5, 10, 25, 50 }; 9 10 int main()11 {12     //freopen("D:\\txt.txt", "r", stdin);13     int s;14     while (cin >> s)15     {16         memset(d, 0, sizeof(d));17         d[0] = 1;18         for (int i = 0; i < 5; i++)19         {20             for (int j = a[i]; j <= s; j++)21                 d[j] += d[j - a[i]];22         }23         cout << d[s] << endl;24     }25     return 0;26 }

 

UVa 674 Coin Change(完全背包)