确定从设置的总和到目标值的双精度组合是否存在 [英] Determine if any combinations of doubles from a set sum to target value
问题描述
我在工作中遇到了一个问题，这让我有些困惑.我需要验证是否可以从药丸剂量大小的任何组合中构造出给定剂量的药物.
I have a problem at work that has me a little stumped. I need to validate that a given dose of a medication can be constructed from any combination of pill dose sizes.
例如
dose = 400.0
sizes= [15.0, 30.0, 45.0]
400不能通过这些值的任何总和来创建(至少我认为是对的).但是，如果将变量更改为:
400 can not be created by any sum of those values (at least I think thats true). However if the variables were changed to:
dose = 400.0
sizes = [10.0, 15.0, 30.0]
我会期望结果为true，因为10x40 =400.或者如果这是senario:
I would expect a result of true because 10x40 = 400. Or if this was the senario:
dose = 405.0
sizes = [2.5, 15.0, 30.0, 100.0]
由于4x100 + 2X2.5 = 405，我也希望得到真实的结果.
I would also expect a true result becuase 4x100 + 2X2.5 = 405.
您将如何编写此算法?它似乎与 Subset Sum 算法有关，但在我的情况下，我想允许多个任何设置项的出现都将成为解决方案的一部分.
How would you approach writing this algorithm? It seems to be related to a Subset Sum algorithm, but in my case I want to allow multiple occurrences of any set item to be part of the solution.
推荐答案
以下 Java 实现解决了双精度值的问题.
The following Java implementation solves your problem for double values.
注意- Java因其不准确而闻名处理基于double/float的算术.但是，对于较低的精度，此解决方案就足够了.自然地，该算法可以用编码语言实现，该编码语言不会受到诸如C ++之类的精度问题的困扰.通过公差阈值检查更新了算法.这意味着现在也可以处理更高的精度.感谢 aschepler 指出了一个有问题的精度用例.
Note - Java is known for its inaccuracy when handling double/float based arithmetics. However, for lower precisions, this solution should suffice. Naturally, this algorithm can be implemented in coding languages which do not suffer as much from the precision problem, such as C++. Updated the algorithm with a tolerance threshold check. This means finer precision is now also handled. Thanks to aschepler for pointing out a problematic precision use case.
已实现了两种算法(基于经典的硬币更改问题)使用在线Java编译器:
Two algorithms have been implemented (based on the classical coin change problem) using an online java compiler:
- 仅返回一个布尔值的布尔值，指示是否存在提供给定总和的子集
- 第一个算法的扩展，其中列出了子集中使用的值
代码如下:
import java.util.*;
public class MyClass {
public static void main(String args[]) {
double set[] = {2.5, 15.0, 30.0, 100.0};
double sum = 405.0;
int n = set.length;
if (count(set, n, sum))
System.out.println("Found a subset with given sum");
else
System.out.println("No subset with given sum");
List<Double> listing = new ArrayList<Double>();
if (countList(set, n, sum,listing))
System.out.println("Found a subset with given sum: " + listing);
else
System.out.println("No subset with given sum");
}
public static boolean count( double S[], int m, double n)
{
// If n is near 0 then there is 1 solution
// (do not include any coin)
if (n >= -0.00001 && n <= 0.00001)
return true;
// If n is less than 0 then no
// solution exists
if (n < 0)
return false;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <=0 && n > 0)
return false;
// count is true if one of the solutions (i) including S[m-1] (ii) excluding S[m-1] is true
return count( S, m - 1, n ) ||
count( S, m, n-S[m-1] );
}
public static boolean countList( double S[], int m, double n, List<Double> listing)
{
// If n is near 0 then there is 1 solution
// (do not include any coin)
if (n >= -0.00001 && n <= 0.00001)
return true;
// If n is less than 0 then no
// solution exists
if (n < 0)
return false;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <=0 && n > 0)
return false;
// count is true if one of the solutions (i) including S[m-1] (ii) excluding S[m-1] is true
List<Double> with = new ArrayList<>();
with.add(S[m-1]);
List<Double> without = new ArrayList<>();
boolean withResult = countList( S, m, n-S[m-1], with );
boolean withoutResult = countList( S, m - 1, n, without );
if(withResult) {
listing.addAll(with);
}
else if (withoutResult) {
listing.addAll(without);
}
return withResult || withoutResult;
}
}
输出:
Found a subset with given sum
Found a subset with given sum: [100.0, 100.0, 100.0, 100.0, 2.5, 2.5]
这是更具挑战性的输入:
And here is a more challenging input:
double set[] = {2.5, 15.0, 30.0, 100.0, 0.2, 0.3};
double sum = 165.9;
Found a subset with given sum
Found a subset with given sum: [0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 100.0, 2.5, 2.5, 2.5, 2.5, 2.5]
还有:
double set[] = {0.2, 0.3, 2.5, 15.0, 30.0, 100.0};
double sum = 148.6;
Found a subset with given sum
Found a subset with given sum: [100.0, 30.0, 15.0, 2.5, 0.3, 0.3, 0.3, 0.2]
以下精确修复程序:
double set[] = {0.05, 0.012, 0.008};
double sum = 0.1;
Found a subset with given sum
Found a subset with given sum: [0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.008, 0.012]
参考文献:
这篇关于确定从设置的总和到目标值的双精度组合是否存在的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
