首页 > 代码库 > UVa 242 邮票和信封（完全背包）
UVa 242 邮票和信封（完全背包）
https://vjudge.net/problem/UVA-242
题意：
输入s（每个信封能粘贴的最多邮票数量）和若干邮票组合，选出最大连续邮资最大的一个组合（最大连续邮资也就是用s张以内的邮票来凑1,2,3,4...n,如果无法凑成n+1，那么最大值也就是n了）。如果有多个最大值，则优先考虑邮票数少的，其次考虑邮票面值最大的那个更小的。
思路：
完全背包问题。
完全背包是物品无限，在这里和题意相符合，每种邮票也是可以无限使用的。最大连续邮资就相当于一个背包容量，d[i]表示当最大连续邮资为i时所需要的最少的邮票数量，如果d[i]>s，说明 i 是无法凑成的，最大连续邮资也就是 i-1 了。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn = 25; 8 const int INF = 0x3f3f3f3f; 9 10 int s, n, m;11 int a[maxn];12 int dp[1005];13 int ans[25];14 15 16 int main()17 {18 //freopen("D:\\txt.txt", "r", stdin);19 while (cin >> s && s)20 {21 int best = 0; //最大连续邮资22 int Max=INF; //最大邮票的值23 int number = INF; //邮票数量24 cin >> n;25 for (int i = 0; i < n; i++)26 {27 cin >> a[0];28 for (int j = 1; j <= a[0]; j++)29 cin >> a[j];30 memset(dp, INF, sizeof(dp));31 dp[0] = 0;32 int now = 0;33 for (int j = 1; j <= s*a[a[0]]+1; j++)34 {35 for (int k = 1; k <= a[0] && j >= a[k]; k++)36 dp[j] = min(dp[j], dp[j - a[k]] + 1);37 if (dp[j]>s)38 {39 now = j - 1;40 break;41 }42 }43 if (now > best) //此时的最大连续邮资大于了之前的44 {45 best = now;46 number = a[0];47 Max = a[a[0]];48 memcpy(ans, a, sizeof(a));49 }50 else if (now == best) //如果相等时51 {52 if (a[0] < number) //首先考虑邮票数量少的53 {54 number = a[0];55 Max = a[a[0]];56 memcpy(ans, a, sizeof(a));57 }58 else if (a[a[0]] < Max) //如果邮票数量一样多，则优先考虑邮票最大的那张更小的59 {60 Max = a[a[0]];61 memcpy(ans, a, sizeof(a));62 }63 }64 }65 printf("max coverage =%4d :", best);66 for (int i = 1; i <= number; i++)printf("%3d", ans[i]);67 puts("");68 }69 return 0;70 }
UVa 242 邮票和信封（完全背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。