求和在一定范围内的所有可能的组合

Question

所以我和一些同事谈过，我目前面临的问题实际上是相当具有挑战性的。这个问题背后的背景与质谱和软件给出的不同峰的结构有关。在

但要把它分解成一个优化问题，我有一定的目标值。我也有各种输入的列表，我希望它们的总和尽可能接近目标。在

作为一个例子，这里是我所拥有的。

List of inputs: [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]

Target value: 1800.71

我想找出所有可能的输入组合，它们的和在1800.71的0.5以内。所以总和可以在1800.21到1801.21之间。在

我已经知道有两个输入可以是：

^{pr2}$

以及

^{3}$

我不想找到使我尽可能接近目标值的组合；我对目标值0.5以内的所有可能的组合感兴趣。在

如果有人能帮我解决这个问题，我将不胜感激！在

Answer 1

我实现了一个递归来获取输入列表中所有值的组合，该组合的总和在阈值范围内。输出在list out（和与组合列表的元组）中。我没有把它全部打印出来，因为它太大了）。在

lst = [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]
target = 1800.71

def find_combination(lst, target, current_values=[], curr_index=0, threshold=0.5):
    s = sum(current_values)

    if abs(s - target) <= threshold:
        yield s, tuple(current_values)

    elif s - target < 0:
        for i in range(curr_index, len(lst)):
            yield from find_combination(lst, target, current_values + [lst[i]], i)

    elif s - target > 0:
        curr_index += 1
        if curr_index > len(lst) - 1:
            return

        yield from find_combination(lst, target, current_values[:-1] + [lst[curr_index]], curr_index)

out = []
for v in find_combination(sorted(lst, reverse=True), target):
    out.append(v)

out = [*set(out)]

print('Number of combinations: {}'.format(len(out)))

## to print the output:
# for (s, c) in sorted(out, key=lambda k: k[1]):
#   print(s, c)

印刷品：

^{pr2}$

编辑：过滤掉重复项。在

Answer 2

与其允许多个值，不如为每个值计算一个整数因子。在

对于你的问题，我得到了988个结果。在

import math
import time

def combinator(tolerance, target, inputs):

    # Special case for inputs with one element, speeds up computation a lot
    if len(inputs) == 1:
        number = inputs[0]
        result_min = int(math.ceil((target-tolerance)/number))
        result_max = int(math.floor((target+tolerance)/number))
        for factor in range(result_min, result_max+1):
            yield [factor]
        return

    # Special case for no inputs, just to prevent infinite recursion 
    if not inputs:
        return

    number = inputs[-1]
    max_value = int(math.floor((target + tolerance)/number))

    for i in range(max_value+1):
        for sub_factors in combinator(tolerance, target-i*number, inputs[:-1]):
            sub_factors.append(i)
            yield sub_factors

def main():
    inputs = [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]
    target = 1800.71

    tolerance = 0.5

    t_start = time.perf_counter()
    results = list(combinator(tolerance, target, inputs))
    t_end = time.perf_counter()

    for result in results:
        result_str = ""
        result_value = 0
        for factor, value in zip(result, inputs):
            if not factor:
                continue
            if result_str != "":
                result_str += " + "
            result_str += "{}* {}".format(factor, value)
            result_value += factor*value
        print("{:.2f}".format(result_value) + " =\t[" + result_str + "]") 

    print("{} results found!".format(len(results)))
    print("Took {:.2f} milliseconds.".format((t_end-t_start)*1000))

if __name__ == "__main__":
    main()

^{pr2}$

---

我还在Rust中重新实现了相同的算法。在

在您的问题上的表现：

• Python：
• 生锈：~0.7 ms

代码如下：

use std::time::Instant;

fn combinator(tolerance : f32, target: f32, inputs: &[f32]) -> Vec<Vec<i32>>{

    let number = match inputs.last() {
        Some(i) => i,
        None => return vec![]
    };

    if inputs.len() == 1 {
        let result_min = ((target-tolerance)/number).ceil() as i32;
        let result_max = ((target+tolerance)/number).floor() as i32;
        return (result_min..=result_max).map(|x| vec![x]).collect();
    }

    let max_value = ((target + tolerance)/number).floor() as i32;

    let mut results = vec![];
    for i in 0..=max_value {
        for mut sub_factors in combinator(tolerance, target - i as f32 * number, &inputs[..inputs.len()-1]) {
            sub_factors.push(i);
            results.push(sub_factors);
        }
    }

    results
}

fn print_result(factors: &[i32], values: &[f32]){
    let sum : f32 = factors.iter()
        .zip(values.iter())
        .map(|(factor,value)| *factor as f32 * *value)
        .sum();
    println!("{:.2} =\t[{}]", sum,
             factors.iter()
                    .zip(values.iter())
                    .filter(|(factor, _value)| **factor > 0)
                    .map(|(factor, value)| format!("{}* {}", factor, value))
                    .collect::<Vec<String>>()
                    .join(", "));
}

fn main() {
    let inputs = vec![18.01, 42.01, 132.04, 162.05, 203.08, 176.03];
    let target = 1800.71;

    let tolerance = 0.5;

    let t_start = Instant::now();
    let results = combinator(tolerance, target, &inputs);
    let duration = t_start.elapsed().as_micros() as f64;

    for result in &results {
        print_result(&result, &inputs);
    }

    println!("{} results found!", results.len());
    println!("Took {} milliseconds", duration / 1000.0);
}

1801.00 =   [100* 18.01]
1800.96 =   [93* 18.01, 3* 42.01]
1800.92 =   [86* 18.01, 6* 42.01]
...
1800.35 =   [5* 18.01, 3* 42.01, 9* 176.03]
1800.33 =   [2* 42.01, 1* 132.04, 9* 176.03]
1800.35 =   [3* 18.01, 1* 162.05, 9* 176.03]
988 results found!
Took 0.656 milliseconds

---

而且，只是为了好玩，这些都是你问题的确切解决方案。一共有5个。在

1800.71 =   [12* 18.01, 1* 42.01, 2* 162.05, 6* 203.08]
1800.71 =   [13* 18.01, 2* 42.01, 2* 132.04, 6* 203.08]
1800.71 =   [16* 18.01, 7* 42.01, 6* 203.08]
1800.71 =   [52* 18.01, 1* 42.01, 1* 132.04, 1* 162.05, 3* 176.03]
1800.71 =   [54* 18.01, 4* 42.01, 1* 132.04, 3* 176.03]

Answer 3

另一个与现有的好答案相同的答案。我发现使用范围而不是目标+公差更简单，并且使用一个简单的（未优化的）递归解决方案，这似乎足够快速地找到您的用例的大约1000个答案。在

更改为使用生成器/产量或优化单值情况并不会改变所有结果所需的时间，尽管如果有管道，则可能会发现这很有用。在

def fuzzy_coins(vals, lower, upper):
    '''
    vals: [Positive]
    lower: Positive
    upper: Positive
    return: [[Int]]
    Returns a list of coefficients for vals such that the dot
    product of vals and return falls between lower and upper.
    '''
    ret = []
    if not vals:
        if lower <= 0 <= upper:
            ret.append(())
    else:
        val = vals[-1]
        for i in xrange(int(upper / val) + 1):
            for sub in fuzzy_coins(vals[:-1], lower, upper):
                ret.append(sub + (i,))
            lower -= val
            upper -= val
    return ret

即使如此，在Python2.7和3.6中也需要大约100ms的时间

^{pr2}$

例如：用法：

from __future__ import print_function
import pprint
import time


def main():
    vals = [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]
    target = 1800.71
    fuzz = .5

    lower = target - fuzz
    upper = target + fuzz
    start = time.time()
    coefs = fuzzy_coins(vals, lower, upper)
    end = time.time()
    pprint.pprint(sorted(
        ('%.2f' % sum(c * v for c, v in zip(coef, vals)), coef)
        for coef in coefs
    ))
    print('Took %.5fs to get %d results' % (end - start, len(coefs)))