XFEEDToolBox

using XFEEDToolBox.Core.Models;

namespace XFEEDToolBox.Core.Planning;

public sealed record CargoCandidate(string Commodity, string Name, long BuyPrice, long SellPrice, int Limit)
{
    public long ProfitPerTon => SellPrice - BuyPrice;
}
public sealed record CargoSolution(IReadOnlyList<TradeOrder> Orders, bool ProvenOptimal, int Nodes)
{
    public decimal Profit => Orders.Sum(x => x.Profit);
}

/// <summary>Integer bounded knapsack with both cash and tonnage constraints, plus explicit node budget.</summary>
public static class CargoOptimizer
{
    public static CargoSolution Optimize(IEnumerable<CargoCandidate> source, int capacity, decimal budget, int nodeBudget = 2500, CancellationToken token = default)
    {
        var goods = source.Where(x => x.BuyPrice > 0 && x.ProfitPerTon > 0 && x.Limit > 0)
            .OrderByDescending(x => x.ProfitPerTon).ThenBy(x => x.BuyPrice).ThenBy(x => x.Commodity, StringComparer.Ordinal).ToArray();
        if (capacity <= 0 || budget <= 0 || goods.Length == 0) return new([], true, 0);
        var current = new int[goods.Length];
        var best = new int[goods.Length];
        decimal bestProfit = 0, bestCost = 0;
        var nodes = 0;
        var truncated = false;

        void Remember(decimal profit, decimal cost)
        {
            if (profit > bestProfit || profit == bestProfit && cost < bestCost)
            { bestProfit = profit; bestCost = cost; Array.Copy(current, best, current.Length); }
        }

        void Seed(IEnumerable<int> order)
        {
            Array.Clear(current);
            var hold = capacity; var cash = budget; decimal profit = 0;
            foreach (var i in order)
            {
                var q = (int)Math.Min(Math.Min(goods[i].Limit, hold), Math.Min(int.MaxValue, decimal.Floor(cash / goods[i].BuyPrice)));
                current[i] = q; hold -= q; cash -= (decimal)q * goods[i].BuyPrice; profit += (decimal)q * goods[i].ProfitPerTon;
            }
            Remember(profit, budget - cash);
        }
        Seed(Enumerable.Range(0, goods.Length));
        Seed(Enumerable.Range(0, goods.Length).OrderByDescending(i => (decimal)goods[i].ProfitPerTon / goods[i].BuyPrice));
        Seed(Enumerable.Range(0, goods.Length).OrderBy(i => goods[i].BuyPrice));
        Array.Clear(current);

        void Search(int index, int hold, decimal cash, decimal profit, decimal cost)
        {
            token.ThrowIfCancellationRequested();
            if (++nodes > nodeBudget) { truncated = true; return; }
            Remember(profit, cost);
            if (index >= goods.Length || hold == 0 || cash <= 0) return;
            decimal byHold = 0, bestRoi = 0;
            var remaining = hold;
            for (var i = index; i < goods.Length; i++)
            {
                var q = Math.Min(remaining, goods[i].Limit);
                byHold += (decimal)q * goods[i].ProfitPerTon; remaining -= q;
                bestRoi = Math.Max(bestRoi, (decimal)goods[i].ProfitPerTon / goods[i].BuyPrice);
            }
            var upper = profit + Math.Min(byHold, cash * bestRoi);
            if (upper <= bestProfit) return;
            var g = goods[index];
            var max = (int)Math.Min(Math.Min(g.Limit, hold), Math.Min(int.MaxValue, decimal.Floor(cash / g.BuyPrice)));
            for (var q = max; q >= 0; q--)
            {
                if (nodes >= nodeBudget) { truncated = true; break; }
                current[index] = q;
                Search(index + 1, hold - q, cash - (decimal)q * g.BuyPrice, profit + (decimal)q * g.ProfitPerTon, cost + (decimal)q * g.BuyPrice);
                current[index] = 0;
            }
        }
        Search(0, capacity, budget, 0, 0);
        var orders = goods.Select((g, i) => new TradeOrder(g.Commodity, g.Name, best[i], g.BuyPrice, g.SellPrice)).Where(x => x.Quantity > 0).ToArray();
        return new(orders, !truncated, nodes);
    }
}