题意分析

题目要求为邮政服务设计一个程序，通过合理选择邮票面值，在信封尺寸限制下（最多使用 $S$ 枚邮票）实现连续无间隙的邮资覆盖。输入包含多组测试数据，每组给出最大邮票数量 $S$ 和 $N$ 个面值集合，需找出能覆盖最大连续邮资范围的面值集合。若存在多个解，优先选择面值数量少的；若面值数量相同，则选择最大面值较小的。例如，使用 1 美分和 3 美分两种面值，最多 5 枚邮票时，能覆盖 1 至 13 美分的所有邮资。

解题思路

代码采用动态规划求解。对每个面值集合，首先计算可能的最大邮资值 $maxv = S$ 最大面值。通过完全背包算法构建 $dp$ 数组，其中 $dp[k]$ 表示凑出邮资 $k$ 所需的最少邮票数。遍历所有可能的邮资，若某个邮资 $k$ 无法用不超过 $S$ 枚邮票凑出（即 $dp[k] > S$），则最大连续覆盖范围为 $k-1$。遍历所有面值集合后，按题目要求的优先级（覆盖范围、面值数量、最大面值）选择最优解并输出。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define inf 1000000
using namespace std;
int a[20][20];
int dp[2005];
int num[20];
int n, ans, p, s, t, maxv;
int main()
{
    while (scanf("%d", &s) != EOF, s)
    {
        scanf("%d", &n);
        ans = 0; t = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
            for (int j = 0; j < num[i]; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 0; i < n; i++)
        {
            maxv = s * a[i][num[i] - 1];
            for (int j = 0; j <= maxv; j++)
            {
                dp[j] = inf;
            }
            dp[0] = 0;
            for (int j = 0; j < num[i]; j++)
            {
                for (int k = a[i][j]; k <= maxv; k++)
                {
                    dp[k] = min(dp[k], dp[k - a[i][j]] + 1);
                }
            }
            int temp = 0;
            for (int j = 0; j <= maxv; j++)
            {
                if (dp[j] > s)
                {
                    temp = j - 1;
                    break;
                }
                if (j == maxv)
                    temp = maxv;
            }
            if (temp > ans)
            {
                ans = temp;
                t = i;
            }
            else if (temp == ans)
            {
                if (num[i] < num[t])
                {
                    t = i;
                }
                else if (num[i] == num[t])
                {
                    if (a[i][num[i] - 1] < a[t][num[t] - 1])
                        t = i;
                }
            }
        }
        printf("max coverage = %d :", ans);
        for (int i = 0; i < num[t]; i++)
        {
            printf(" %d", a[t][i]);
        }
        printf("\n");

    }
    return 0;
}