动态规划 - 如何快速找出几个数相加最接近目标数的组合的算法？

Question

求一个计算几个数相加最接近目标数的组合 的算法。

有一个数组[8477, 7980, 4732, 1337, 714, ...n] 注意：可以反复使用同一个数进行相加，例如8477+8477+1337
数组中的元素相加接近某个目标值的区间：例如 大于17993且小于19051;

要求找出最短组合，就是假设有4个数相加，3个数相加，2个数相加的都满足需求的，那要取2个数相加的组合。

尽可能快的算法，暴力循环，太慢了~

需求javascript版的~

Answer 1

使用 glpk.js 库来进行整数线性规划
使用javascript
首先，确保你已经安装了 glpk.js：
npm install glpk.js

const glpk = require('glpk.js');

function findMinCombination(nums, lowerBound, upperBound) {
    // 定义目标函数：最小化元素数量
    const c = Array(nums.length).fill(1);

    // 定义不等式约束：和在 lowerBound 和 upperBound 之间
    const A = [
        { vars: nums.map((num, i) => ({ name: `x${i}`, coef: num })), bnds: { type: glpk.GLP_LO, ub: 0, lb: lowerBound } },
        { vars: nums.map((num, i) => ({ name: `x${i}`, coef: num })), bnds: { type: glpk.GLP_UP, ub: upperBound, lb: 0 } }
    ];

    // 定义变量的边界：每个变量都是非负整数
    const bounds = nums.map((_, i) => ({ name: `x${i}`, type: glpk.GLP_LO, ub: Infinity, lb: 0 }));

    // 创建模型
    const lp = {
        name: 'find_min_combination',
        objective: {
            direction: glpk.GLP_MIN,
            name: 'obj',
            vars: nums.map((_, i) => ({ name: `x${i}`, coef: 1 }))
        },
        subjectTo: A,
        bounds: bounds
    };

    // 使用整数线性规划求解
    const result = glpk.solve(lp);

    // 检查是否找到有效解
    if (result.result.status === glpk.GLP_OPT) {
        return Math.floor(result.result.z);
    } else {
        return -1;
    }
}

// 示例用法
const nums = [8477, 7980, 4732, 1337, 714];
const lowerBound = 17993;
const upperBound = 19051;
const result = findMinCombination(nums, lowerBound, upperBound);
console.log(`所需的最小元素数量: ${result}`);

使用 scipy.optimize 库的整数线性规划
使用python

from scipy.optimize import linprog
import numpy as np

def find_min_combination(nums, lower_bound, upper_bound):
    # 定义目标函数：最小化元素数量
    c = np.ones(len(nums))

    # 定义不等式约束：和在 lower_bound 和 upper_bound 之间
    A = np.vstack([nums, -np.array(nums)])
    b = np.array([upper_bound, -lower_bound])

    # 定义变量的边界：每个变量都是非负整数
    bounds = [(0, None) for _ in nums]

    # 使用整数线性规划求解
    res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='highs-ipm')

    # 检查是否找到有效解
    if res.success and res.fun != np.inf:
        return int(res.fun)
    else:
        return -1

# 示例用法
nums = [8477, 7980, 4732, 1337, 714]
lower_bound = 17993
upper_bound = 19051
result = find_min_combination(nums, lower_bound, upper_bound)
print(f"所需的最小元素数量: {result}")