确定是否有从设定和到目标值的任何双倍组合

Question

我在工作中遇到了一个让我有点困惑的问题。我需要验证给定剂量的药物是否可以由药丸剂量大小的任意组合构成。

例如

dose = 400.0
sizes= [15.0, 30.0, 45.0]

400不能由这些值的任何和来创建（至少我认为这是真的）。但是，如果变量更改为：

dose = 400.0 
sizes = [10.0, 15.0, 30.0]

我希望结果为真，因为10x40=400。或者如果这是塞纳里奥：

dose = 405.0
sizes = [2.5, 15.0, 30.0, 100.0]

我还希望得到一个真实的结果，因为4x100 2X2.5=405。

你会如何写这个算法？它似乎与子集和算法有关，但在我的例子中，我希望允许任何集合项的多次出现成为解决方案的一部分。

Answer 1

一种标准方法是：

1. 将你所有的双打都表示为有理数，因此[2.5,15.0,30.0,100.0]变成[5/2,15,30,100]
2. 乘以分母的LCM得到整数大小：[5,30,60,200]剂量为810
3. 检查您所需的剂量是否是GCF大小的倍数：是的，810是5的倍数（如果不是，则显然无法获得）
4. 除以尺寸的GCF：[1,6,12,40]和剂量162
5. 将标准动态规划解决方案应用于“硬币兑换问题”。网上有很多关于这个问题的资源，比如这个问题

Answer 2

下面的Java实现解决了双值问题。

注意-Java在处理基于双/浮点运算时以其不准确性而闻名。然而，对于较低的精度，这种解决方案应该足够了。自然地，这种算法可以在不太受精度问题影响的编码语言中实现，比如C语言。用公差阈值检查更新了算法。这意味着现在也可以处理更精细的精度。感谢ascheler指出了一个有问题的精度用例。

使用在线java编译器实现了两种算法（基于经典的硬币变化问题）：

• 一种简单地返回一个布尔值，指示是否有提供给定和的子集

代码如下：

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,html" target="_blank">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]

这里有一个更具挑战性的输入：

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]

参考资料：

• 维基百科中的更改问题定义
• 硬币兑换问题-回顾和基于C的解决方案
• 硬币交换问题 — 贪婪还是动态规划？
• Java中的Float和double“不准确”结果