Find K arrays that sum up to a given array with a certain accuracy

Question

Let's say I have set containing thousands of arrays (let's fix it to 5000 of arrays) of a fixed size (size = 8) with non negative values. And I'm given another array of the same size with non negative values (Input Array). My task is to select some subset of arrays, with the condition that if I sum them together (summation of vectors) I would get the resultant array which is very close to a given Input Array with the desired accuracy (+-m).

For example if the desired result (input array) is (3, 2, 5) and accuracy = 2 Then of course the best set would be the one that would sum up to exactly (3,2,5) but also any solution of the following form would be ok (3 +- m, 2 +- m, 5 +- m).

The question is what could be the right algorithmic approach here? It is similar to multi dimensional sack problem, but there is no cost optimization section in my task.

At least one solution is required which meets the constraints. But several would be better, so that it would be possible to have a choice.

Answer 1

This is kind of extended knapsack problem. We know that it is NPC task to do which mean = we cannot use bruteforce and try all possibilities. It is just not computable with current computers.

What we can do is use some heuristic. One simple and useful is the simulated annealing. The principle is quite simple - at beginning of your algorithm, when the temperature is high - you are not afraid to take even the "at the moment worse solution" (which can actually lead to the best possible solution). So at beginning you take almost anything. Then you start cooling and more cool you are, the more causius you are so you are trying to improve your solution more and more and risk less and less.

The gifs on wiki are actually nice example: https://en.wikipedia.org/wiki/Simulated_annealing

I have also implemented solution that at the end prints whats the inputArray and what is your solution and the "negative score" (the less the better).

You are not guaranteed to get best/valid solution, but you can basically run this in some while cycle until you find solution good enough or you hit some threshold (like if you do not find good solution after running 100x times, you say "data not valid" or take the best of these "not good" solutions)

class Simulation {
    constructor(size, allArrSize, inputArrayRange, ordinarySize, maxDif, overDifPenalisation) {
        this.size = size;
        this.allArrSize = allArrSize;
        this.inputArrayRange = inputArrayRange;
        this.ordinarySize = ordinarySize;
        this.maxDif = maxDif;
        this.overDifPenalisation = overDifPenalisation;

        this.allArr = [];
        this.solutionMap = new Map();
        for (let i = 0; i < allArrSize; i++) {
            let subarr = [];
            for (let j = 0; j < size; j++) {
                subarr.push(Math.round(Math.random() * ordinarySize));
            }
            this.allArr.push(subarr);
        }

        this.temperature = 100;
        this.inputArray = [];
        for (let i = 0; i < size; i++) {
            this.inputArray.push(Math.round(Math.random() * inputArrayRange));
        }
    }

    findBest() {
        while (this.temperature > 0) {
            const oldScore = this.countScore(this.solutionMap);
            // console.log(oldScore);
            let newSolution = new Map(this.solutionMap);

            if (this.addNewOrRemove(true)) {
                const newCandidate = Math.floor(Math.random() * this.allArrSize);
                newSolution.set(newCandidate, true);
            } else if (this.addNewOrRemove(false)) {
                const deleteCandidate = Math.floor(Math.random() * this.solutionMap.size);
                Simulation.deleteFromMapByIndex(newSolution, deleteCandidate);
            } else {
                const deleteCandidate = Math.floor(Math.random() * this.solutionMap.size);
                Simulation.deleteFromMapByIndex(newSolution, deleteCandidate);
                const newCandidate = Math.floor(Math.random() * this.allArrSize);
                newSolution.set(newCandidate, true);
            }

            const newScore = this.countScore(newSolution);
            if (newScore < oldScore) {
                this.solutionMap = newSolution;
            } else if ((newScore - oldScore) / newScore < this.temperature / 300) {
                this.solutionMap = newSolution;
            }

            this.temperature -= 0.001;
        }

        console.log(this.countScore(this.solutionMap), 'Negative Score');
        console.log(this.sumTheSolution(this.solutionMap).toString(), 'Solution');
        console.log(this.inputArray.toString(), 'Input array');
        console.log('Solution is built on these inputs:');            
        this.solutionMap.forEach((val, key) => console.log(this.allArr[key].toString()))
    }

    addNewOrRemove(addNew) {
        const sum = this.sumTheSolution(this.solutionMap);

        let dif = 0;
        sum.forEach((val, i) => {
            const curDif = this.inputArray[i] - val;
            if (curDif < -this.maxDif) {
                dif -= 1;
            }
            if (curDif > this.maxDif) {
                dif += 1;
            }
        });

        let chance;
        if (addNew) {
            chance = (dif + this.size - 1) / (this.size * 2);
        } else {
            chance = (-dif + this.size - 1) / (this.size * 2);
        }

        return chance > Math.random();
    }

    countScore(solution) {
        const sum = this.sumTheSolution(solution);

        let dif = 0;
        sum.forEach((val, i) => {
            let curDif = Math.abs(this.inputArray[i] - val);
            if (curDif > this.maxDif) {
                curDif += (curDif - this.maxDif) * this.overDifPenalisation;
            }
            dif += curDif;
        });

        return dif;
    }

    sumTheSolution(solution) {
        const sum = Array(this.size).fill(0);
        solution.forEach((unused, key) => this.allArr[key].forEach((val, i) => sum[i] += val));
        return sum;
    }

    static deleteFromMapByIndex(map, index) {
        let i = 0;
        let toDelete = null;
        map.forEach((val, key) => {
            if (index === i) {
                toDelete = key;
            }
            i++;
        });
        map.delete(toDelete);
    }
}

const simulation = new Simulation(8, 5000, 1000, 100, 40, 100);
simulation.findBest();

You can play a bit with numbers to get waht you need (the speed of cooling, how it affects probability, some values in constructor etc.)