，所以我与一些同事进行了交谈，而我目前遇到的问题实际上很具有挑战性。这个问题背后的上下文与质谱和为软件提供的不同峰分配结构有关。
，但是要将其分解为优化问题，我有一定的目标值。我也有各种输入的列表，我想尽可能接近目标。
，例如，这就是我拥有的。
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之间。
我已经知道两个输入可能是：
[18.01, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05, 162.05] **which gives a sum of 1800.59**
和
[18.01, 18.01, 203.08, 203.08, 203.08, 162.05, 203.08, 18.01, 18.01, 18.01, 18.01, 18.01, 18.01, 18.01, 18.01, 18.01, 18.01, 42.01, 162.05, 203.08, 203.08] **which gives a sum 1800.71**
我不想找到使我尽可能接近目标价值的组合；我对目标值的0.5之内的所有可能组合感兴趣。
如果有人能帮助我解决这个问题，我将非常感谢它！
而不是允许多个值，只要计算每个值的整数因子要快很多。
对于您的问题，我得到了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()
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 11.48 milliseconds.
我还在Rust中重新完成了相同的算法。
在您的问题上的表现：
- python： 〜12 ms
- 锈： 〜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]
与现有罚款答案相同的另一个答案。我发现使用范围而不是目标 公差并使用琐碎的(未取代(递归解决方案更简单，该解决方案似乎足够快，可以找到您用例的约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
即使这样，这需要〜100ms的Python 2.7和3.6
[('1800.33', (0, 2, 1, 0, 0, 9)),
('1800.35', (3, 0, 0, 1, 0, 9)),
('1800.35', (5, 3, 0, 0, 0, 9)),
('1800.38', (0, 10, 0, 2, 0, 6)),
('1800.38', (1, 11, 2, 0, 0, 6)),
...
('1800.92', (86, 6, 0, 0, 0, 0)),
('1800.94', (88, 2, 1, 0, 0, 0)),
('1800.96', (91, 0, 0, 1, 0, 0)),
('1800.96', (93, 3, 0, 0, 0, 0)),
('1801.00', (100, 0, 0, 0, 0, 0))]
Took 0.10885s to get 988 results
例如。用法：
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)))
我实现了递归以获取输入列表中的所有值组合，该组合的总和在阈值之内。输出位于列表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)
打印：
Number of combinations: 988
编辑：滤除重复项。