POJ 1276 (多重背包) Cash Machine

浏览数：25 / 时间：2015年06月20日

题意：

有n种纸币，已知每种纸币的面值和数量，求所能凑成的不超过cash的最大总面值。

分析：

这道题自己写了一下TLE了，好可耻。。

找了份比较简洁的代码抄过来了。。poj1276

技术分享 
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxn = 12;
 5 const int maxp = 100000 + 10;
 6 
 7 bool vis[maxp];//是否到达总面值i
 8 int used[maxp];//到达总面值i时，该种纸币所用的数量
 9 int a[maxn], b[maxn];//每种纸币的数量以及面值
10 
11 int cash, n;
12 
13 int main()
14 {
15     //freopen("in.txt", "r", stdin);
16 
17     while(scanf("%d", &cash) == 1)
18     {
19         scanf("%d", &n);
20         for(int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]);
21 
22         memset(vis, false, sizeof(vis));
23         vis[0] = true;
24         for(int i = 0; i < n; ++i)
25         {
26             memset(used, 0, sizeof(used));
27             for(int j = b[i]; j <= cash; ++j)
28                 if(vis[j-b[i]] && !vis[j] && used[j-b[i]] < a[i])
29                 { vis[j] = true; used[j] = used[j-b[i]] + 1; }
30         }
31 
32         for(int i = cash; i >= 0; --i) if(vis[i]) { printf("%d\n", i); break; }
33     }
34 
35     return 0;
36 }
代码君

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： class style 代码 com log src html http si class style 代码 com log src html http si

相关文章

随机文章

您可能还喜欢

您可能还喜欢