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 了。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f; int s, n, m;
int a[maxn];
int dp[];
int ans[]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> s && s)
{
int best = ; //最大连续邮资
int Max=INF; //最大邮票的值
int number = INF; //邮票数量
cin >> n;
for (int i = ; i < n; i++)
{
cin >> a[];
for (int j = ; j <= a[]; j++)
cin >> a[j];
memset(dp, INF, sizeof(dp));
dp[] = ;
int now = ;
for (int j = ; j <= s*a[a[]]+; j++)
{
for (int k = ; k <= a[] && j >= a[k]; k++)
dp[j] = min(dp[j], dp[j - a[k]] + );
if (dp[j]>s)
{
now = j - ;
break;
}
}
if (now > best) //此时的最大连续邮资大于了之前的
{
best = now;
number = a[];
Max = a[a[]];
memcpy(ans, a, sizeof(a));
}
else if (now == best) //如果相等时
{
if (a[] < number) //首先考虑邮票数量少的
{
number = a[];
Max = a[a[]];
memcpy(ans, a, sizeof(a));
}
else if (a[a[]] < Max) //如果邮票数量一样多，则优先考虑邮票最大的那张更小的
{
Max = a[a[]];
memcpy(ans, a, sizeof(a));
}
}
}
printf("max coverage =%4d :", best);
for (int i = ; i <= number; i++)printf("%3d", ans[i]);
puts("");
}
return ;
}