Rolling ship plate calculator

rolling-ship-calc.js

function closestSubsetSum(nums, target, maxIterations, prices) {
    let closest = 0;
    let cheapest = 100_000_000_000;
    let closestSubset = [];
    let found = false;
    let count = 0;

    nums.sort((a, b) => b - a); // Sort in descending order for better pruning

    function findSubset(index, currentSubset, currentSum) {
        count++;

        if (count > 100_000_000) {
            return;
        }

        if (currentSum > target || currentSubset.length > 7) return;

        if (Math.abs(target - currentSum) <= Math.abs(target - closest)) {
            closest = currentSum;
            closestSubset = [...currentSubset];

            if (closest === target) {
                found = true;
                const price = closestSubset.map(x => prices[x].price).reduce((sum, curr) => sum + curr);
                if (price < cheapest) {
                    cheapest = price;

                    console.log(`Cheapest perfect solution found ${price.toLocaleString()}:`, closestSubset.map(x => prices[x].name));
                }
            }
        }

        for (let i = index; i < nums.length; i++) {
            if (currentSum + nums[i] <= target || currentSubset.length < 7) {
                findSubset(i + 1, [...currentSubset, nums[i]], currentSum + nums[i]);
            }
        }
    }

    findSubset(0, [], 0);

    if (!found) {
        console.log("Numbers used for closest sum:", closestSubset.map(x => x.toLocaleString()));
        console.log("Closest ", closest.toLocaleString());
        console.log("Target ", target.toLocaleString());
    }
}

const m = (name, price) => ({ name, price });

const prices = {
    // 100mm
    20_000: m('100mm Fed Navy', 1_480_000),
    25_000: m('100mm Citadella', 20_000),
    32_500: m('100mm Cristalline', 28_200),
    35_000: m('100mm Rolled Tungsten', 27_300),
    // 37_500: m('100mm T2', 420_000),

    90_000: m('200mm Fed Navy', 8_100_000),
    100_000: m('200mm Syndicate', 73_100_000),
    120_000: m('200mm Crystalline', 109_000),
    140_000: m('200mm Rolled Tungsten', 107_000),
    // 150_000: m('200mm T2', 1_280_000),

    225_000: m('400mm Fed Navy', 14_400_000),
    250_000: m('400mm Syndicate', 73_700_000),
    300_000: m('400mm Crystalline', 224_000),
    350_000: m('400mm Rolled Tungsten', 236_000),
    // 375_000: m('400mm T2', 1_120_000),

    900_000: m('800mm Fed Navy', 17_900_000),
    1_000_000: m('800mm Syndicate', 84_700_000),
    1_200_000: m('800mm Crystalline', 641_000),
    1_350_000: m('800mm Rolled Tungsten', 649_000),
    // 1_450_000: m('800mm T2', 4_840_000),

    2_250_000: m('1600mm Fed Navy', 33_900_000),
    2_500_000: m('1600mm Syndicate', 95_600_000),
    3_000_000: m('1600mm Crystalline', 1_100_000),
    3_500_000: m('1600mm Rolled Tungsten', 1_140_000),
    // 3_750_000: m('1600mm T2', 9_910_000),
};

const numbers = Object.keys(prices).map(x => Array(7).fill(Number(x))).flat();

const shipWeight = 87_000_000;
const target = 100_000_000;
const toBeFilled = target - shipWeight;
const maxIterationsToSearch = 500_000_000;

closestSubsetSum(numbers, toBeFilled, maxIterationsToSearch, prices);