背景

业务中有一个功能，可以使用优惠券抵扣字数，优惠券面额有 300 字、500 字和 800 字，张数随机。在用户下单的时候需要为其自动推荐最佳优惠券组合，同时为了保证优惠券不浪费，最多只能溢出小于 300 字。
- 例如 900 字的订单，有 2 张 800 字优惠券，若全部使用，则会浪费 700 字，对用户体验不好。对于这种情况，只为用户自动选择 1 张 800 字的优惠券即可。
那么这个问题可以抽象为一个有条件限制的多重背包问题。

题目描述

你有若干张优惠券，每张优惠券可以抵扣一定的字数，规则如下：
1. 优惠券面额为300、500、800，每种张数有限
2. 每次用户选择一个目标字数target（为100的整数倍）
请你从宜有的优惠券中选出若干张，使得总字数sum满足
1. sum >= target （必须覆盖目标字数）
2. sum - target < 300（溢出必须严格小于300，即最小优惠券面额）
如果找不到满足上述条件的组合，退而求其次，返回一个 sum <= target的组合，要求它尽可能接近target。
如果仍然无法组成任意组合，则返回null
你需要输出所选优惠券的张数，格式为[used_300, used_500, used_800]

示例1

输入：

count300 = 2
count500 = 1
count800 = 1
target = 400

输出：
1
[0, 1, 0]

示例2

输入：

count300 = 0
count500 = 0
count800 = 2
target = 900

输出：
1
[0, 0, 1]
解释：2 张 800 总共 1600，溢出太大不满足要求；但用 1 张 800 可以覆盖 800，是次优方案中最接近的。

示例3

输入：

count300 = 0
count500 = 0
count800 = 0
target = 500

输出：
1
null

解题思路

多重背包模型

这是一个典型的多重背包问题（每种物品数量有限），不同点在于加入了“溢出限制”和“次优解兜底”逻辑。

转换分析

将三种优惠券视为三类物品：每种物品有一个固定价值（300、500、800）和数量限制。
目标是尽可能刚好填满一个区间 [target, target + 299]，即我们在背包容量不止为 target，而是允许范围内多出来一点点。
如果找不到上述组合，则考虑向下逼近 target。

步骤分解

定义状态：使用一维布尔数组 dp[i] 表示当前是否能凑出字数 i；使用 path[i] 保存达到该字数所用的优惠券组合（记录 [300张数, 500张数, 800张数]）。
初始化：dp[0] = true，表示不使用任何券时可以达到 0；其余为 false。
状态转移：对于每种优惠券，进行多重背包枚举（按张数逐一添加），倒序更新 dp 状态。
路径记录：每次成功转移状态 s -> s + val，记录 path 中的券张数组合。
寻找最优解：从 target 开始往上查找至 target + 299，一旦发现有解即为最优。
次优策略：若无法满足条件 1 和 2，从 target - 1 反向查找最接近的组合。
无解情况：若所有路径都不可达，则返回 null。

Java实现

定义状态存储结构

用于记录到达某个金额时，三种面额分别用了多少张券。这样我们就能在求出最终结果时，知道怎么凑出来的。

static class State {
    int count300, count500, count800;

    State(int c300, int c500, int c800) {
        this.count300 = c300;
        this.count500 = c500;
        this.count800 = c800;
    }
}

主函数声明
- 参数：count300 / count500 / count800：每种券的数量
- target：目标字数（必须是100整数倍）
  - 返回值：长度为3的数组，表示每种券用了多少张；或 null 表示无解。
    1
    public static int[] solve(int count300, int count500, int count800, int target)
初始化变量
- values：每种优惠券面额
- counts：每种面额可用张数
- maxSum：最大搜索金额（比如 target=700，我们最多能接受 sum=999）
- 为什么是 target + 299？因为溢出最多允许小于300，也就是 sum - target < 300。所以最多考虑到 target + 299。
  1
  2
  3
  int[] values = {300, 500, 800};
  int[] counts = {count300, count500, count800};
  int maxSum = target + 299;
初始化dp列表
- dp[s] == true 表示：我们能用若干优惠券凑出总额 s
- 初始时只有 dp[0] = true（表示啥也不用）
- path[s] 记录达到金额 s 时所使用的券张数组合。
  1
  2
  3
  4
  boolean[] dp = new boolean[maxSum + 1];
  dp[0] = true;
  State[] path = new State[maxSum + 1];
  path[0] = new State(0, 0, 0);

状态转移

这里用了多重背包朴素解法（O(n * sum)），核心点：

遍历券种类 → 遍历张数 → 遍历背包容量（倒序）
每次发现 dp[s] 可达，就尝试扩展到 dp[s + val]

用 path[] 记录从哪一步转移来的，便于追溯券组合

for (int i = 0; i < 3; i++) { // 遍历三种面额
    int val = values[i];      // 当前面额
    int num = counts[i];      // 当前种类最多可用张数

    for (int used = 0; used < num; used++) { // 按张数来转移
        for (int s = maxSum - val; s >= 0; s--) { // 倒序避免重复使用
            if (dp[s] && !dp[s + val]) {
                dp[s + val] = true;

                // 记录路径（怎么从 s -> s+val）
                State prev = path[s];
                path[s + val] = new State(
                    prev.count300 + (i == 0 ? 1 : 0),
                    prev.count500 + (i == 1 ? 1 : 0),
                    prev.count800 + (i == 2 ? 1 : 0)
                );
            }
        }
    }
}

从「合法区间」找最优解

先查满足 ≥ target 且溢出小于 300 的

for (int s = target; s <= target + 299; s++) {
    if (dp[s]) {
        State res = path[s];
        return new int[]{res.count300, res.count500, res.count800};
    }
}

再查满足 ≤ target 的最大值

for (int s = target - 1; s >= 0; s--) {
    if (dp[s]) {
        State res = path[s];
        return new int[]{res.count300, res.count500, res.count800};
    }
}

如果目标区间内没有任何组合满足要求，就从目标往下找尽可能接近的组合。

完整代码

static class State {
    int count300, count500, count800;

    State(int c300, int c500, int c800) {
        this.count300 = c300;
        this.count500 = c500;
        this.count800 = c800;
    }
}

public static int[] solve(int count300, int count500, int count800, int target) {
    int[] values = {300, 500, 800};
    int[] counts = {count300, count500, count800};
    int maxSum = target + 299;

    boolean[] dp = new boolean[maxSum + 1];
    dp[0] = true;

    State[] path = new State[maxSum + 1];
    path[0] = new State(0, 0, 0);

    for (int i = 0; i < 3; i++) {
        int val = values[i];
        int num = counts[i];
        for (int used = 0; used < num; used++) {
            for (int s = maxSum - val; s >= 0; s--) {
                if (dp[s] && !dp[s + val]) {
                    dp[s + val] = true;
                    State prev = path[s];
                    path[s + val] = new State(
                        prev.count300 + (i == 0 ? 1 : 0),
                        prev.count500 + (i == 1 ? 1 : 0),
                        prev.count800 + (i == 2 ? 1 : 0)
                    );
                }
            }
        }
    }

    for (int s = target; s <= target + 299; s++) {
        if (dp[s]) {
            State res = path[s];
            return new int[]{res.count300, res.count500, res.count800};
        }
    }

    for (int s = target - 1; s >= 0; s--) {
        if (dp[s]) {
            State res = path[s];
            return new int[]{res.count300, res.count500, res.count800};
        }
    }

    return null;
}