algorithm - 找到以一定精度求和到给定数组的 K 个数组

Question

假设我设置了包含数千个非负值的固定大小 (size = 8) 的数组(让我们将其固定为 5000 个数组)。我得到了另一个具有非负值的相同大小的数组(输入数组)。我的任务是选择数组的一些子集，条件是如果我将它们加在一起(向量求和)，我将得到结果数组，该数组非常接近具有所需精度(+-m)的给定输入数组。

例如，如果所需的结果(输入数组)是 (3, 2, 5) 且准确度 = 2 那么当然最好的集合将是一个总和为 (3,2,5) 的集合，但也可以是以下形式的任何解决方案 (3 +- m, 2 +- m, 5 +- m) .

问题是这里正确的算法方法是什么？它类似于多维麻袋问题，但我的任务中没有成本优化部分。

至少需要一个满足约束条件的解决方案。但有几个会更好，这样就可以有选择。

Answer 1

这是一种扩展背包问题。我们知道这是 NPC 的任务，这意味着我们不能使用暴力并尝试所有可能性。目前的计算机无法计算它。

我们可以做的是使用一些启发式方法。一种简单而有用的方法是模拟退火。原理很简单——在你的算法开始时，当温度很高时——你甚至不怕采用“目前最糟糕的解决方案”(这实际上可以导致最好的解决方案)。所以一开始你几乎什么都拿。然后你开始冷静下来，你越冷静，你就越谨慎，所以你会越来越多地尝试改进你的解决方案，风险越来越小。

wiki 上的 gif 实际上是很好的例子:https://en.wikipedia.org/wiki/Simulated_annealing

我还实现了解决方案，最后打印什么是 inputArray 以及你的解决方案是什么以及“负分”(越少越好)。

你不能保证得到最佳/有效的解决方案，但你基本上可以在某个 while 循环中运行它，直到你找到足够好的解决方案或者你达到某个阈值(比如如果你在运行 100 次后没有找到好的解决方案，你说“数据无效”或采取最好的这些“不好”的解决方案)

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();

你可以玩一些数字来获得你需要的东西(冷却速度，它如何影响概率，构造函数中的一些值等)