题目链接:https://vjudge.net/contest/146179#problem/D
题意:
信封上最多贴S张邮票。有N个邮票集合,每个集合有不同的面值。问哪个集合的最大连续邮资最大,输出最大连续邮资和集合元素。最大连续邮资是用S张以内邮票面值凑1,2,3...到n+1凑不出来了,最大连续邮资就是n。如果不止一个集合结果相同,输出集合元素少的,如果仍相同,输出最大面值小的。
这个题意,刘汝佳的书上输出刚好写反。
分析:
先看一组数据。求最大连续邮资,那我想用二分啊,看这个答案是不是符合的,其实,在求这个答案是不是符合的,会重复计算,还不如按顺序计算。
这个从1开始算,算到某一个数,他的最少票数>s,就达到要求的了。那么这就是一个无穷背包问题了。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int maxn = 25;
6 int a[maxn][maxn];
7 int s,n;
8 int dp[1005];
9 int ans[25];
10
11 const int INF = 0x3f3f3f3f;
12
13 int main()
14 {
15 while(scanf("%d",&s),s)
16 {
17 scanf("%d",&n);
18 for(int i=0; i<n; i++)
19 {
20 scanf("%d",&a[i][0]);
21 for(int j=1; j<=a[i][0]; j++)
22 scanf("%d",&a[i][j]);
23
24 memset(dp,INF,sizeof(dp));
25 dp[0] = 0;
26 for(int j=1; j<1005; j++)
27 {
28 for(int k=1; k<=a[i][0]&&j-a[i][k]>=0; k++)
29 {
30 dp[j] = min(dp[j],dp[j-a[i][k]]+1);
31 }
32 if(dp[j]>s)
33 {
34 ans[i] = j-1;
35 break;
36 }
37 }
38 }
39
40 int anss = -1,cnt = 0;
41 for(int i=0; i<n; i++)
42 {
43 if(ans[i]>anss)
44 {
45 anss = ans[i];
46 cnt = i;
47 }
48 else if(ans[i]==anss&&a[i][0]<a[cnt][0]) cnt = i; //票数最少
49 else if(ans[i]==anss&&a[i][0]==a[cnt][0])
50 {
51 bool ok = false;
52 for(int j=a[i][0]; j>=0; j--)
53 {
54 if(a[i][j]<a[cnt][j])
55 {
56 ok = true;
57 break;
58 }
59 else if(a[i][j]>a[cnt][j]) break;
60 }
61 if(ok) cnt = i;
62 }
63 }
64 printf("max coverage =%4d :",anss);
65 for(int i=1; i<=a[cnt][0]; i++)
66 printf("%3d",a[cnt][i]);
67 puts("");
68 }
69 return 0;
70 }
原文链接: https://www.cnblogs.com/TreeDream/p/6240989.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/246855
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!