凑发票算法：经典背包问题的变种

在日常工作中，特别是报销或财务处理时，经常会遇到这样的问题：如何从一堆发票中找到金额满足某个值的最优组合？本文将基于 C#，使用背包问题的思路来卷这个问题，并详细讲解其设计和实现细节。

问题

假设我们有一组发票，每张发票以文件名的形式存储，文件名包含发票金额，例如 酒店-996.35.pdf 打车-251.00 医疗-404.00 。我们的目标是从这些发票中，找到金额总和 至少等于目标金额 的最优组合，并且总金额尽可能接近目标金额。以最大程度的节省发票以供下次报销使用。

例如：我需要报销1000元，现有发票如下：

酒店-996.00.pdf
咖喱饭-35.00.pdf
文具-7.00.pdf

显然，要凑1000元的发票，最优解是使用 酒店-996.00.pdf + 文具-7.00.pdf = 1003.00 元，这样的话，咖喱饭-35.00.pdf 可用于下次报销使用。在文件较少的情况下，肉眼就能找到最优组合，但当文件夹里有几十、上百张发票的时候，人工凑发票就会让你996。

算法设计

要解决这个问题，我们可以将其看作一个 背包问题的变种，即在给定一组发票的情况下，找到满足条件的金额组合。本文的算法采用 回溯法 来实现，逐步尝试每种可能的组合，并记录满足条件的最佳结果。

背包问题（英语：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。

首先，我们定义一个 Invoice 类，用来存储发票的文件名和金额：

private class Invoice
{
    public string FileName { get; set; }
    public double Amount { get; set; }
}

从当前目录中读取所有 PDF 文件，并将文件名存储到一个列表中：

// 获取当前目录
string currentDirectory = Path.GetDirectoryName(Util.CurrentQueryPath);

// 获取当前目录下所有PDF文件的文件名
string[] pdfFiles = Directory.GetFiles(currentDirectory, "*.pdf");

// 创建一个List<string>集合来存储文件名
List<string> invoiceFileNames = new List<string>();

// 将每个文件的文件名添加到List<string>集合中
foreach (string file in pdfFiles)
{
    // 只获取文件名，不包括路径
    string fileName = Path.GetFileName(file);
    invoiceFileNames.Add(fileName);
}

发票的文件名采用了固定的格式，例如 加班福报-996.35.pdf，我们通过解析文件名来提取金额：

var invoices = invoiceFileNames.Select(fileName =>
{
    var parts = Path.GetFileNameWithoutExtension(fileName).Split('-');
    return new Invoice
    {
        FileName = fileName,
        Amount = double.Parse(parts[1], CultureInfo.InvariantCulture)
    };
}).ToList();

这里我们将文件名按 - 分割，提取第二部分作为金额，并将其转换为 double 类型（其实金融计算更适合用decimal，但不要在意这些细节）

核心算法部分是一个回溯函数，用来尝试所有可能的发票组合：

void FindCombination(List<Invoice> currentCombination, int startIndex, double currentSum)
{
    // 如果当前组合的金额满足条件，且比之前的最佳组合更优，则更新最佳组合
    if (currentSum >= targetAmount && (bestCombination == null || currentSum < bestAmount))
    {
        bestAmount = currentSum;
        bestCombination = new List<Invoice>(currentCombination);
        return;
    }

    // 遍历剩余的发票，尝试加入当前组合
    for (int i = startIndex; i < invoices.Count; i++)
    {
        currentCombination.Add(invoices[i]);
        FindCombination(currentCombination, i + 1, currentSum + invoices[i].Amount);
        currentCombination.RemoveAt(currentCombination.Count - 1); // 回溯
    }
}

回溯的核心逻辑：

递归搜索：从起始位置开始，逐步尝试将每张发票加入当前组合。
剪枝条件：如果当前组合的金额已经满足条件且优于之前的组合，则更新最佳组合。
回溯：在递归返回时，移除最后一张发票，尝试其他可能的组合。

找到最佳组合后，我们将结果输出到控制台：

if (selectedInvoices != null)
{
    Console.WriteLine($"满足至少{targetAmount}的最优发票组合:");
    Console.WriteLine("----------------------------------");
    
    foreach (var invoice in selectedInvoices)
    {
        Console.WriteLine(invoice.FileName);
    }
    
    Console.WriteLine("----------------------------------");
    Console.WriteLine(selectedInvoices.Sum(p => p.Amount));
}
else
{
    Console.WriteLine("发票不够");
}

示例运行

当前目录有发票文件如下：

医疗-404.00.pdf
咖喱饭-35.00.pdf
打车-251.00.pdf
文具-7.00.pdf
酒店-996.00.pdf

设定目标金额为 290.00 元，程序输出结果为：

满足至少290的最优发票组合:
----------------------------------
咖喱饭-35.00.pdf
打车-251.00.pdf
文具-7.00.pdf
----------------------------------
293

设定目标金额为 1000.00 元，程序输出结果为：

满足至少1000的最优发票组合:
----------------------------------
文具-7.00.pdf
酒店-996.00.pdf
----------------------------------
1003

直观图示

拿文章开头的问题来说，在 酒店-996.00.pdf 咖喱饭-35.00.pdf 文具-7.00.pdf 中寻找满足1000元的最佳发票组合的过程是将问题转化为一个递归决策树，每个节点表示当前组合的金额总和和发票选择状态。算法从根节点开始，每次递归尝试包含或不包含当前发票，直到遍历所有可能的组合。

Start (Sum = 0, Combination = [])
├── Include 酒店-996.00.pdf (Sum = 996.00, Combination = [酒店-996.00.pdf])
│   ├── Include 咖喱饭-35.00.pdf (Sum = 1031.00, Combination = [酒店-996.00.pdf, 咖喱饭-35.00.pdf])
│   │   ├── Include 文具-7.00.pdf (Sum = 1038.00, Combination = [酒店-996.00.pdf, 咖喱饭-35.00.pdf, 文具-7.00.pdf])
│   │   └── Exclude 文具-7.00.pdf (Sum = 1031.00, Combination = [酒店-996.00.pdf, 咖喱饭-35.00.pdf])
│   └── Exclude 咖喱饭-35.00.pdf (Sum = 996.00, Combination = [酒店-996.00.pdf])
│       ├── Include 文具-7.00.pdf (Sum = 1003.00, Combination = [酒店-996.00.pdf, 文具-7.00.pdf]) -> 满足条件，记录最佳组合
│       └── Exclude 文具-7.00.pdf (Sum = 996.00, Combination = [酒店-996.00.pdf])
├── Exclude 酒店-996.00.pdf (Sum = 0, Combination = [])
    ├── Include 咖喱饭-35.00.pdf (Sum = 35.00, Combination = [咖喱饭-35.00.pdf])
    │   ├── Include 文具-7.00.pdf (Sum = 42.00, Combination = [咖喱饭-35.00.pdf, 文具-7.00.pdf])
    │   └── Exclude 文具-7.00.pdf (Sum = 35.00, Combination = [咖喱饭-35.00.pdf])
    └── Exclude 咖喱饭-35.00.pdf (Sum = 0, Combination = [])
        ├── Include 文具-7.00.pdf (Sum = 7.00, Combination = [文具-7.00.pdf])
        └── Exclude 文具-7.00.pdf (Sum = 0, Combination = [])

算法从金额为 0 的空组合开始。每个分支表示对当前发票的两种选择：Include 或 Exclude。叶子节点表示所有发票都已处理完成，此时检查组合是否满足条件，即金额 >= 1000 元。如果当前金额已经满足条件，则记录组合并停止进一步递归。

从递归树中可以看出，满足至少 1000 元的组合有以下路径：

路径 A：包含 酒店-996.00.pdf 和 文具-7.00.pdf ，总金额：996.00 + 7.00 = 1003.00
路径 B：包含 酒店-996.00.pdf 和 咖喱饭-35.00.pdf ，总金额：996.00 + 35.00 = 1031.00

最终，算法选择金额最接近目标值的路径A。

算法复杂度分析

时间复杂度：由于回溯法会尝试所有可能的组合，其时间复杂度为 $O(2^n)$ ，其中 $n$ 是发票的数量。

空间复杂度：递归调用栈的深度为。

虽然时间复杂度较高，但对于发票数量较少的场景（例如几十张发票），该算法依然可以在可接受的时间内完成计算。

总结

本文通过一个实际的发票金额匹配问题，详细介绍了如何使用 C# 实现一个基于回溯法的凑发票算法。该算法的核心在于递归搜索所有可能的组合，并通过剪枝优化来提高效率。希望本文的讲解能够帮助大家更好地理解回溯法的应用场景，并为实际工作中的类似问题提供参考解决方案。

Microsoft MVP for Azure

凑发票算法：经典背包问题的变种

问题

算法设计

示例运行

直观图示

算法复杂度分析

总结

Comments