Billing system - Programming：计费规则的数据结构设计

2026-10-24数据小许

结论

可以用“字符到计费规则”的映射保存配置，例如 Map<Character, PricingRule>。每条规则包含若干组数量和价格：

A -> (1 个 2 元), (3 个 5 元)
B -> (1 个 3 元)
C -> (1 个 1 元), (4 个 3 元)

计算时，先统计每个字符出现的次数，分别算出每种字符的最低价格，再把结果相加。

如果每种字符只有一个组合价，用除法和取模就能计算。如果以后可能增加多个组合档位，则应使用动态规划，不能依赖简单的贪心或固定取模。

数据结构设计

一个价格组合可以建模为：

record PriceTier(int quantity, long price) {}

其中：

quantity 表示该价格覆盖的数量；
price 表示总价；
金额应使用最小货币单位保存，例如“分”，以免遇到 double 的精度问题。

每种字符对应一组价格：

Map<Character, List<PriceTier>> rules = Map.of(
    'A', List.of(
        new PriceTier(1, 2),
        new PriceTier(3, 5)
    ),
    'B', List.of(
        new PriceTier(1, 3)
    ),
    'C', List.of(
        new PriceTier(1, 1),
        new PriceTier(4, 3)
    )
);

示例中的金额仍以整数“元”为单位。实际计费系统建议统一使用“分”。

可扩展的计算方式

下面的 Java 示例使用动态规划，从所有合法组合中找出最低价格。以后即使增加 2A = 4、5A = 7 等规则，也不需要修改计算逻辑。

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BillingSystem {

    public record PriceTier(int quantity, long price) {
        public PriceTier {
            if (quantity <= 0) {
                throw new IllegalArgumentException("quantity must be positive");
            }
            if (price < 0) {
                throw new IllegalArgumentException("price must not be negative");
            }
        }
    }

    private final Map<Character, List<PriceTier>> rules;

    public BillingSystem(Map<Character, List<PriceTier>> rules) {
        this.rules = Map.copyOf(rules);
    }

    public long calculate(String input) {
        Map<Character, Integer> counts = new HashMap<>();

        for (char item : input.toCharArray()) {
            if (!rules.containsKey(item)) {
                throw new IllegalArgumentException(
                    "No billing rule configured for: " + item
                );
            }

            counts.merge(item, 1, Integer::sum);
        }

        long total = 0;

        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            List<PriceTier> tiers = rules.get(entry.getKey());
            total = Math.addExact(
                total,
                minimumPrice(entry.getValue(), tiers)
            );
        }

        return total;
    }

    private long minimumPrice(int count, List<PriceTier> tiers) {
        long unreachable = Long.MAX_VALUE;
        long[] dp = new long[count + 1];

        for (int i = 1; i <= count; i++) {
            dp[i] = unreachable;
        }

        dp[0] = 0;

        for (int current = 1; current <= count; current++) {
            for (PriceTier tier : tiers) {
                if (tier.quantity() <= current
                        && dp[current - tier.quantity()] != unreachable) {
                    long candidate = Math.addExact(
                        dp[current - tier.quantity()],
                        tier.price()
                    );

                    dp[current] = Math.min(dp[current], candidate);
                }
            }
        }

        if (dp[count] == unreachable) {
            throw new IllegalArgumentException(
                "The configured rules cannot price quantity: " + count
            );
        }

        return dp[count];
    }

    public static void main(String[] args) {
        Map<Character, List<PriceTier>> rules = Map.of(
            'A', List.of(
                new PriceTier(1, 2),
                new PriceTier(3, 5)
            ),
            'B', List.of(
                new PriceTier(1, 3)
            ),
            'C', List.of(
                new PriceTier(1, 1),
                new PriceTier(4, 3)
            )
        );

        BillingSystem billing = new BillingSystem(rules);
        System.out.println(billing.calculate("ABCCBAACCA"));
    }
}

输出：

计算过程

输入 ABCCBAACCA 中各字符的数量如下：

A：4 个
B：2 个
C：4 个

对应的价格是：

A: 3 个组合价 5 + 1 个单价 2 = 7
B: 2 × 3 = 6
C: 4 个组合价 = 3

总价: 7 + 6 + 3 = 16

什么时候可以直接使用取模

按照当前规则，A 可以直接这样计算：

long price = (count / 3) * 5 + (count % 3) * 2;

C 也可以用同样的方法：

long price = (count / 4) * 3 + (count % 4) * 1;

不过，这种写法需要同时满足以下条件：

每种字符只有一个组合档位；
组合价不高于相同数量的单价；
尽可能多地使用组合价一定能得到最低价格。

增加规则后，这些条件不一定成立。例如：

1A = 3
3A = 8
4A = 9

购买 6 个 A 时，使用两个 3A 需要 16，而使用一个 4A 加两个单价只需要 15。因此，“优先使用某个组合”的算法可能算错，使用动态规划更稳妥。

注意事项

上述设计假设同类字符可以合并计费，字符在字符串中的顺序不会影响价格。
每种规则最好包含 quantity = 1 的档位，否则某些数量可能无法计价。
遇到未配置规则的字符时应明确报错，不要默认按零价格处理。
实际金额建议使用整数“分”或 BigDecimal，不要使用 float 或 double。
如果输入数量很大而价格档位很少，可以进一步利用规则的周期性或最短路算法优化。一般订单规模下，复杂度为 O(n × k) 的动态规划已经足够，其中 n 是某种字符的数量，k 是其价格档位数。