下列Java
实现解决了双值的问题。
Note - Java 以其不准确而闻名 http://www.drdobbs.com/jvm/javas-floating-point-imprecision/240168744处理基于双精度/浮点的算术时。但是,对于较低的精度,此解决方案应该足够了。当然,该算法可以用不太受精度问题影响的编码语言(例如 C++)来实现。
通过容差阈值检查更新了算法。这意味着现在还可以处理更精细的精度。谢谢阿舍普勒 https://stackoverflow.com/users/459640/aschepler指出一个有问题的精度用例。
已经实现了两种算法(基于经典的硬币找零问题 https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/) using 一个在线java编译器 https://www.jdoodle.com/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]
这是一个更具挑战性的输入:
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]
参考:
- 维基百科中的变革问题定义 https://en.wikipedia.org/wiki/Change-making_problem
- 硬币找零问题 - 回顾和基于 C++ 的解决方案 https://www.hackerrank.com/challenges/coin-change/problem
- 硬币交换问题 — 贪婪还是动态规划? https://medium.com/@emailarunkumar/coin-exchange-problem-greedy-or-dynamic-programming-6e5ebe5a30b5
- Java中的float和double“不准确”结果 http://piotrnowicki.com/2011/02/float-and-double-in-java-inaccurate-result/