首页 > 代码库 > hdu acm 2844 Coins 解题报告

hdu acm 2844 Coins 解题报告

2024-07-15 13:08:53   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844

题目意思：有A1，A2，...，An 这 n 种面值的钱，分别对应的数量是C1，C2，...，Cn。问根据这么多数量的钱 能组成多少个 <= m 的钱。

      如果用多重背包来做，超时了...如果用记忆化搜索，还是...超时= =.....

      这个方法是网上搜的，觉得好神奇，能看懂一些。

      它是根据完全背包的思路做的，但是需要限制每种币种的使用数量，于是就多了个used[] 数组来记录了。 ! f[j]表示之前没有组成 j 这么多的钱，f[j] = 1 就表示已经组成过 j 那么多的钱了，下次再遇到同样能构成 j 那么多的钱就不要再重复算了。 这个f[j-A[i]] 有一点点让我难以理解，应该就是 如果在不超过C[i] 数量（used[j-A[i]]）的情况下，用一定数量的 A[i] 再加上之前用过的 A[i-1] ，A[i-2]，...，A[1] （当然也可以不用，也可以用部分） 这些币值能能够组成 j 这么多钱。

      还有这句：used[j] = used[j-A[i]] + 1;  也有一点不太懂，不知道为什么要从used[j-A[i]] 前提下 +1......  

     代码中注释部分可能有误导别人的成分，欢迎指出不足（哎~~~没办法啦，网上的这份代码，好像没有人写过注释，我也是按自己理解啦= =）

      

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 1e5 + 5; 7 const int N = 100 + 5; 8  9 int A[N], C[N];10 int f[maxn], used[maxn];11 12 int main()13 {14     int n, m;15     while (scanf("%d%d", &n, &m) != EOF && (m+n))16     {17         memset(f, 0, sizeof(f));18         for (int i = 0; i < n; i++)19             scanf("%d", &A[i]);20         for (int i = 0; i < n; i++)21             scanf("%d", &C[i]);22         f[0] = 1;23         int ans = 0;24         for (int i = 0; i < n; i++)25         {26             for (int j = 0; j <= m; j++)27                 used[j] = 0;    // used[j]表示当前这种面值为j时用了A[i]多少次，它的使用时限制A[i]被使用的数量，否则就可以用无限个了28             for (int j = A[i]; j <= m; j++)29             {30                 if (!f[j] && f[j-A[i]] && used[j-A[i]] < C[i])  // 用f[j]表示能组成这价值为j的钱和不能（0与1）， f[j-A[i]] 表示之前能组成j-A[i]这么多钱31                 {32                 // printf("!f[j]: !f[%d];  f[j-A[i]]: f[%d]\n", j, j-A[i]);33                 //    printf("used[j-A[i]]: used[%d] = %d, C[i]: C[%d] = %d\n", j-A[i], used[j-A[i]], i, C[i]);34                     f[j] = 1;35                     used[j] = used[j-A[i]] + 1;  // 组成j这么多钱还需要用多一次A[i]这样的币值36                     ans++;37                 //    printf("used[%d] = %d\n", j, used[j]);38                 //    printf("组成面值为 %d 时用了 A[%d](即 %d) %d 次\n\n", j, i, A[i], used[j]);39                 }40             }41         }42         printf("%d\n", ans);43     }44     return 0;45 }

 

    输出变量图，真诚奉献，真心强大啊~~~

    

   


联系
我们