import java.util.ArrayList;
|
import java.util.Arrays;
|
import java.util.List;
|
|
public class MinimalCombinationSum {
|
|
private static List<Double> bestSolution;
|
private static double target;
|
private static double minDifference;
|
private static final double EPSILON = 1e-10;
|
|
public static List<Double> findBestCombination(Double[] candidates, double targetSum) {
|
bestSolution = null;
|
target = targetSum;
|
minDifference = Double.MAX_VALUE;
|
Arrays.sort(candidates);
|
backtrack(candidates, 0, new ArrayList<>(), 0.0);
|
|
// 如果没有精确解，返回最接近的近似解
|
return bestSolution != null ? bestSolution : new ArrayList<>();
|
}
|
|
private static void backtrack(Double[] candidates, int start,
|
List<Double> current, double currentSum) {
|
// 计算当前和与目标的差值
|
double difference = Math.abs(currentSum - target);
|
|
// 如果找到更优解（差值更小或差值相同但组合更短）
|
if (difference < minDifference - EPSILON ||
|
(Math.abs(difference - minDifference) < EPSILON &&
|
(bestSolution == null || current.size() < bestSolution.size()))) {
|
minDifference = difference;
|
bestSolution = new ArrayList<>(current);
|
}
|
|
// 如果已经找到精确解，不需要继续搜索更长的组合
|
if (minDifference < EPSILON) {
|
return;
|
}
|
|
// 遍历候选数字
|
for (int i = start; i < candidates.length; i++) {
|
double num = candidates[i];
|
|
// 剪枝：如果当前和已经远大于目标值，跳过
|
if (currentSum + num > target + minDifference + EPSILON) {
|
continue;
|
}
|
|
// 跳过重复数字
|
if (i > start && Math.abs(candidates[i] - candidates[i - 1]) < EPSILON) {
|
continue;
|
}
|
|
current.add(num);
|
backtrack(candidates, i + 1, current, currentSum + num);
|
current.remove(current.size() - 1);
|
}
|
}
|
|
public static void main(String[] args) {
|
Double[] candidates1 = {1.5, 2.3, 3.1, 4.7};
|
double target1 = 3.8;
|
System.out.println("候选数字: " + Arrays.toString(candidates1));
|
System.out.println("目标值: " + target1);
|
List<Double> result1 = findBestCombination(candidates1, target1);
|
printResult(result1, target1);
|
|
// Double[] candidates2 = {0.8, 1.2, 1.7, 2.5};
|
// double target2 = 3.9;
|
// System.out.println("\n候选数字: " + Arrays.toString(candidates2));
|
// System.out.println("目标值: " + target2);
|
// List<Double> result2 = findBestCombination(candidates2, target2);
|
// printResult(result2, target2);
|
}
|
|
private static void printResult(List<Double> result, double target) {
|
if (result.isEmpty()) {
|
System.out.println("无解");
|
} else {
|
double sum = result.stream().mapToDouble(Double::doubleValue).sum();
|
if (Math.abs(sum - target) < EPSILON) {
|
System.out.printf("精确解: %s (和=%.2f)\n", result, sum);
|
} else {
|
System.out.printf("近似解: %s (和=%.2f, 与目标相差: %.2f)\n",
|
result, sum, sum - target);
|
}
|
}
|
}
|
}
|
