Un problema común en el ámbito administrativo consiste en seleccionar un conjunto de facturas cuya suma se aproxime lo más posible a un límite preestablecido, por ejemplo, un bono mensual de comida de 500 unidades monetarias. La pregunta es: dado un conjunto de facturas con distintos importes, ¿cuál es la combinación óptima que maximiza el total sin exceder el tope?

Enfoque manual con heurística greedy

Antes de recurrir a herramientas externas, se puede plantear una solución heurística sencilla basada en ordenamiento descendente y acumulación iterativa. La idea consiste en tomar el mayor valor disponible, luego ir agregando elementos restantes mientras la suma no supere el objetivo, y repetir el proceso con los elementos sobrantes.

A continuación se muestra una implementación alternativa que devuelve agrupaciones de valores dentro de un rengo tolerable respecto al objetivo:

using System;
using System.Collections.Generic;
using System.Linq;

internal static class InvoiceOptimizer
{
    public static List<list>> FindOptimalGroups(double[] amounts, double target, double tolerance = 0.5)
    {
        var result = new List<list>>();
        var pool = amounts.OrderByDescending(x => x).ToList();

        while (pool.Count > 0)
        {
            var group = new List<double> { pool[0] };
            pool.RemoveAt(0);

            bool added;
            do
            {
                added = false;
                for (int k = 0; k < pool.Count; k++)
                {
                    double currentSum = group.Sum();
                    if (pool[k] <= target - currentSum - tolerance)
                    {
                        group.Add(pool[k]);
                        pool.RemoveAt(k);
                        added = true;
                        break;
                    }
                }
            } while (added);

            result.Add(group);
        }

        return result;
    }
}
</double></list></list>

Para ejecutarlo y explorar distintos umbrales cercanos al valor deseado, se puede recorrer un rango de cantidades:

internal static class Program
{
    private static void Main()
    {
        string raw = "1, 595, 600, 499, 497, 476, 5, 4, 3, 2, 1, 39, 500, 400, 455, 466, 478, 483, 35, 16, 5, 15, 6, 7, 8, 4, 7, 35, 13, 10, 2, 21, 40, 41, 33, 39, 31, 26, 11, 51, 77, 43, 36, 81, 23, 15, 72, 45, 83, 29, 55, 2, 3, 6, 9, 4, 5, 5, 6, 7, 4, 3";
        double[] invoices = raw.Split(',')
                               .Select(s => Convert.ToDouble(s.Trim()))
                               .ToArray();

        double desired = 450;
        double lowerBound = desired - 10;
        double upperBound = desired + 10;

        for (double limit = lowerBound; limit <= upperBound; limit++)
        {
            PrintGroups(invoices, limit);
        }

        Console.ReadLine();
    }

    private static void PrintGroups(double[] invoices, double limit)
    {
        Console.WriteLine($"--- Objetivo: {limit} ---");
        var groups = InvoiceOptimizer.FindOptimalGroups(invoices, limit);

        foreach (var grp in groups)
        {
            double total = grp.Sum();
            double gap = limit - total;
            Console.WriteLine($"Diferencia: {gap:F2} | Total: {total:F2} | Items: {string.Join(", ", grp)}");
        }
        Console.WriteLine();
    }
}

Este enfoque produce múltiples agrupaciones, pero la heurística greedy no garantiza la solución óptima en términos globales. Para obtener el verdadero valor máximo bajo una restricción, conviene recurrir a un solver especializado.

Solución exacta con Google OR-Tools

Google OR-Tools ofrece un solver de mochila multidimensional mediante branch and bound que resuelve este tipo de problemas de forma exacta y eficiente. El problema de seleccionar facturas para maximizar la suma sin exceder un límite es un caso particular del problema de la mochila, donde los valores y los pesos coinciden.

El paquete NuGet correspondiente es Google.OrTools. Una vez referenciado, la implemantación queda así:

using System;
using System.Collections.Generic;
using Google.OrTools.Algorithms;

public static class KnapsackSolver
{
    public static void Run()
    {
        var solver = new KnapsackSolver(
            KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
            "InvoiceKnapsack");

        long[] itemValues = { 1, 595, 600, 499, 497, 476, 5, 4, 3, 2, 1, 39,
            500, 400, 455, 466, 478, 483, 35, 16, 5, 15, 6, 7, 8, 4, 7, 35,
            13, 10, 2, 21, 40, 41, 33, 39, 31, 26, 11, 51, 77, 43, 36, 81,
            23, 15, 72, 45, 83, 29, 55, 2, 3, 6, 9, 4, 5, 5, 6, 7, 4, 3 };

        long[,] itemWeights = new long[1, itemValues.Length];
        for (int idx = 0; idx < itemValues.Length; idx++)
        {
            itemWeights[0, idx] = itemValues[idx];
        }

        long[] capacities = { 650 };

        solver.Init(itemValues, itemWeights, capacities);
        long bestValue = solver.Solve();

        Console.WriteLine($"Valor óptimo alcanzado: {bestValue}");

        var selectedIndexs = new List<int>();
        long accumulatedWeight = 0;

        for (int i = 0; i < itemValues.Length; i++)
        {
            if (solver.BestSolutionContains((long)i))
            {
                selectedIndexs.Add(i);
                accumulatedWeight += itemWeights[0, i];
            }
        }

        Console.WriteLine($"Peso total acumulado: {accumulatedWeight}");
        Console.WriteLine($"Índices seleccionados: {string.Join(", ", selectedIndexs)}");
    }
}

En este modelo, cada factura se trata como un ítem cuyo valor coincide con su importe. El solver encuentra la combinación de ítems cuyo peso total no excede la capacidad (650 en este ejemplo) y cuyo valor es máximo. Esto garantiza la solución óptima, a diferencia del enfoque greedy que solo aproxima.