My input consists of two arrays. The first array is called dels and looks like this:
const dels = [ // up to 50 possible
{no: 491, weight: 1348},
{no: 492, weight: 694},
{no: 1054, weight: 4104},
{no: 1181, weight: 2636}, // *
{no: 2096, weight: 4084},
{no: 2201, weight: 4064},
{no: 2296, weight: 2364},
{no: 2365, weight: 1670},
{no: 2632, weight: 4084},
{no: 2891, weight: 2424},
{no: 3051, weight: 2414}, // *
];
The second array, sums, holds some values as well:
const sums = [5050, 24836]; // up to 4 possible
While the structure remains fixed, the actual numbers are sourced externally.
I've established that every number in the sums array represents the sum of specific weights from the dels array (each dels item used only once).
Hence, these assumptions hold true:
const sumDels = dels.reduce((a,i) => a + i.weight, 0);
const sumSums = sums.reduce((a,i) => a + i, 0);
sumDels === sumSums // is true
sumDels.every(x => x.weight > 0) // is true
I seek an algorithm that efficiently provides me with potential combinations leading to the given sums.
An example outcome might resemble this:
const goodResult = [ // <-- array of possible combinations (theretically, there could be more than one)
[ // <-- `dels` array mapped with `sumIdx`
{no: 491, sumIdx: 1},
{no: 492, sumIdx: 1},
{no: 1054, sumIdx: 1},
{no: 1181, sumIdx: 0}, // *
{no: 2096, sumIdx: 1},
{no: 2201, sumIdx: 1},
{no: 2296, sumIdx: 1},
{no: 2365, sumIdx: 1},
{no: 2632, sumIdx: 1},
{no: 2891, sumIdx: 1},
{no: 3051, sumIdx: 0}, // *
]
];
An inefficient solution would involve trying out all permutations, but with sums.length==4 and dels.length==50, we're looking at a whopping 1267650600228229401496703205376 possible combinations! Quite overwhelming...