import java.util.ArrayList;
|
import java.util.Arrays;
|
import java.util.List;
|
|
public class CombinationFinder {
|
|
public List<Integer> findCombination(double[] nums, double target) {
|
// 处理等值情况
|
List<Integer> equal = findEqual(nums, target);
|
if (equal != null && !equal.isEmpty()) {
|
return equal;
|
}
|
|
// 处理大于的情况
|
List<Integer> greater = findGreater(nums, target);
|
if (greater != null && !greater.isEmpty()) {
|
return greater;
|
}
|
|
// 处理小于的情况
|
List<Integer> less = findLess(nums, target);
|
return less != null ? less : new ArrayList<>(); // 确保不返回null
|
}
|
|
private List<Integer> findEqual(double[] nums, double target) {
|
int n = nums.length;
|
double[] dp = new double[(int) (target * 100 + 1)]; // 放大100倍处理精度问题
|
Arrays.fill(dp, Double.MAX_VALUE);
|
dp[0] = 0;
|
int[] prev = new int[(int) (target * 100 + 1)];
|
Arrays.fill(prev, -1);
|
|
for (int j = 0; j < n; j++) {
|
int num = (int) (nums[j] * 100); // 放大100倍处理精度问题
|
for (int i = (int) (target * 100); i >= num; i--) {
|
if (dp[i - num] != Double.MAX_VALUE && dp[i - num] + 1 < dp[i]) {
|
dp[i] = dp[i - num] + 1;
|
prev[i] = j;
|
}
|
}
|
}
|
|
if (dp[(int) (target * 100)] == Double.MAX_VALUE) {
|
return null;
|
}
|
|
List<Integer> indices = new ArrayList<>();
|
int current = (int) (target * 100);
|
while (current > 0) {
|
int j = prev[current];
|
if (j == -1) return null;
|
indices.add(j);
|
current -= (int) (nums[j] * 100);
|
}
|
|
return indices;
|
}
|
|
private List<Integer> findGreater(double[] nums, double target) {
|
List<double[]> sorted = new ArrayList<>();
|
for (int i = 0; i < nums.length; i++) {
|
sorted.add(new double[]{nums[i], i});
|
}
|
sorted.sort((a, b) -> Double.compare(b[0], a[0]));
|
|
double sum = 0;
|
List<Integer> indices = new ArrayList<>();
|
for (double[] pair : sorted) {
|
sum += pair[0];
|
indices.add((int) pair[1]);
|
if (sum > target) {
|
return indices;
|
}
|
}
|
|
return null;
|
}
|
|
private List<Integer> findLess(double[] nums, double target) {
|
int n = nums.length;
|
List<Integer> bestIndices = new ArrayList<>();
|
double[] maxSum = {-1.0};
|
for (int k = 1; k <= n; k++) {
|
List<Integer> currentIndices = new ArrayList<>();
|
double[] currentMax = {-1.0};
|
backtrack(nums, target, 0, k, 0.0, 0, currentIndices, currentMax, new ArrayList<>());
|
if (currentMax[0] != -1.0) {
|
if (currentMax[0] > maxSum[0] || (currentMax[0] == maxSum[0] && currentIndices.size() < bestIndices.size())) {
|
maxSum[0] = currentMax[0];
|
bestIndices = new ArrayList<>(currentIndices);
|
}
|
}
|
}
|
|
return bestIndices.isEmpty() ? null : bestIndices;
|
}
|
|
private void backtrack(double[] nums, double target, int start, int k, double currentSum, int count, List<Integer> currentIndices, double[] currentMax, List<Integer> path) {
|
if (count == k) {
|
if (currentSum <= target && currentSum > currentMax[0]) {
|
currentMax[0] = currentSum;
|
currentIndices.clear();
|
currentIndices.addAll(path);
|
}
|
return;
|
}
|
|
for (int i = start; i < nums.length; i++) {
|
if (currentSum + nums[i] > target) continue;
|
path.add(i);
|
backtrack(nums, target, i + 1, k, currentSum + nums[i], count + 1, currentIndices, currentMax, path);
|
path.remove(path.size() - 1);
|
}
|
}
|
|
public static void main(String[] args) {
|
CombinationFinder finder = new CombinationFinder();
|
double[] nums = {3.0, 1.0, 4.0, 2.0};
|
double target = 0.1;
|
List<Integer> result = finder.findCombination(nums, target);
|
System.out.println("最优组合的索引: " + result); // 例如，等值组合可能为索引2（4.0）和3（1.0）
|
}
|
}
|
