在Java中，我应该如何找到数组元素与特定值K最接近（或相等）的可能总和？
例如，对于数组 {19,23,41,5,40,36} 且 K=44，最接近的可能总和为 23+19=42。 我已经为此苦苦挣扎了几个小时；我对动态规划几乎一无所知。顺便说一句，该数组仅包含正数。
您通常会使用动态规划来解决此类问题。然而，这本质上可以归结为保留一组可能的总和并将输入值逐一相加，如以下代码所示，并且具有相同的渐近运行时间：
O(n K)nK下面版本中的常量可能更大，但是我认为代码比动态编程版本更容易理解。
public class Test {
public static void main(String[] args) {
int K = 44;
List<Integer> inputs = Arrays.asList(19,23,41,5,40,36);
int opt = 0; // optimal solution so far
Set<Integer> sums = new HashSet<>();
sums.add(opt);
// loop over all input values
for (Integer input : inputs) {
Set<Integer> newSums = new HashSet<>();
// loop over all sums so far
for (Integer sum : sums) {
int newSum = sum + input;
// ignore too big sums
if (newSum <= K) {
newSums.add(newSum);
// update optimum
if (newSum > opt) {
opt = newSum;
}
}
}
sums.addAll(newSums);
}
System.out.println(opt);
}
}
编辑
关于运行时间的简短说明可能会有用，因为我只是在没有理由的情况下声称
O(n K)显然，初始化和打印结果只需要常数时间，所以我们应该分析双循环。
外层循环遍历所有输入，因此其主体被执行
n内循环遍历到目前为止的所有总和，理论上这可能是一个指数数。 但是，我们使用上限
Ksums[0, K]sumsK+1内部循环内的所有计算都需要常数时间，因此总循环需要
O(K)newSumsK+1addAllO(K)结束：外循环执行
nO(K)O(n K)编辑2
根据要求如何找到导致最佳总和的元素：
除了跟踪单个整数（子列表的总和）之外，您还应该跟踪子列表本身。如果您创建一个新类型，这相对简单（没有 getter/setter 来保持示例简洁）：
public class SubList {
public int size;
public List<Integer> subList;
public SubList() {
this(0, new ArrayList<>());
}
public SubList(int size, List<Integer> subList) {
this.size = size;
this.subList = subList;
}
}
初始化现在变为：
SubList opt = new SubList();
Set<SubList> sums = new HashSet<>();
sums.add(opt);
sumsfor (Integer input : inputs) {
Set<SubList> newSums = new HashSet<>();
// loop over all sums so far
for (SubList sum : sums) {
List<Integer> newSubList = new ArrayList<>(sum.subList);
newSubList.add(input);
SubList newSum = new SubList(sum.size + input, newSubList);
// ignore too big sums
if (newSum.size <= K) {
newSums.add(newSum);
// update optimum
if (newSum.size > opt) {
opt = newSum;
}
}
}
sums.addAll(newSums);
}
private int closestSum(int[] a, int num){
int k=a.length-1;
int sum=0;
Arrays.sort(a);
while(a[k]>num){
k--;
}
for(int i=0;i<k;i++){
for(int j=i+1;j<=k;j++){
if(a[i]+a[j]<=num && a[i]+a[j]>sum)
sum = a[i]+a[j];
}
}
return sum;
}
我会说首先对数组进行排序。那么您的示例将是：arr = {5, 19, 23, 36, 40, 41}。 然后： 1) 取arr[0]和arr[i]，其中i = arr.Size。将其求和，如果总和小于 K，则记录总和与 K 之间的差。 2) 如果 sum > K，则执行步骤 1，但不要使用 arr[i]，而是使用 arr[i-1]，因为我们想要降低总和。 如果求和< K, do step 1, but instead of arr[0], use arr[1], because we want to increase our sum. Keep repeating step2, by either increasing or decreasing the indices, until the indices for the two elements are equal. Then, we know the pair of elements that result in the smallest difference between the sum and K.
----------------编辑解决方案中任意数量的元素----------------
我相信你可能需要一棵树。 这是我的想法：
1) 选择一个数字作为顶部节点。
2）对于集合中的每个数字，创建一个子节点，并为创建的每个分支， 计算该分支的总和。
3）如果总和小于 K，我们再次分支，为集合中的所有元素创建子节点。如果总和大于 K，我们停止，保留总和与 K 之间的差（如果总和< K). If we find a branch with a better sum, then we keep that branch. Repeat this process until all branches are done branching.
使用不同的顶部节点执行步骤 1-3。
Vincent 的答案的一个问题是它需要在内存中保存所有当前列表。这意味着执行时间和内存使用的最坏情况都是 O(2^n)，其中 n 是输入数量。
注意：底部的解决方案代码是 C# 语言，而不是 Java 语言。对于 Java 程序员来说，将解决方案移植到 Java 应该是微不足道的。
为了避免将列表存储在内存中，可以生成候选索引（类似于计数器）。例如，如果有 6 个输入，则要检查的全套可能解决方案将如下所示：
总共有 (2^n - 1) 种组合。
0
1
2
3
4
5
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
0 1 2
0 1 3
0 1 4
0 1 5
0 2 3
0 2 4
0 2 5
0 3 4
0 3 5
0 4 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
0 1 2 3
0 1 2 4
0 1 2 5
0 1 3 4
0 1 3 5
0 1 4 5
0 2 3 4
0 2 3 5
0 2 4 5
0 3 4 5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
0 1 2 3 4
0 1 2 3 5
0 1 2 4 5
0 1 3 4 5
0 2 3 4 5
1 2 3 4 5
0 1 2 3 4 5
该算法最棘手的部分是生成上述类似计数器的索引。进行优化以排除检查输入中 > K 的值。还包括一个附加优化，即对输入进行排序。这允许在不存在可能的解决方案具有总和的情况下停止检查索引 <= K.
public static Subset ClosestElementSum() {
int K = 76;
int[] inputs = new int[] { 19, 23, 41, 5, 40, 36 }; // values must be >= 0
// first do a simple check to see if the sum of all the elements is less than
// the target value, as well as checking the smallest value in the inputs is
// less than the target value
int totalSum = 0;
int minValue = int.MaxValue;
List<int> sortedInputs = new List<int>(); // only contains values < K
for (int i = 0; i < inputs.Length; i++) {
totalSum += inputs[i];
if (inputs[i] < minValue)
minValue = inputs[i];
if (inputs[i] == K)
return new Subset(K, new List<int>(new int[] { K })); // found an exact solution
if (inputs[i] < K)
sortedInputs.Add(inputs[i]);
}
if (minValue > K || sortedInputs.Count == 0)
return null; // no solution possible
if (totalSum <= K) {
// all the inputs added together are still less than or equal to K
// so avoid all the iterations and simply return all the inputs
List<int> list = new List<int>(inputs);
return new Subset(totalSum, list);
}
// the inputs are sorted so that if the sum exceeds the target K value then
// there is no point in checking more solutions. For example, if
// inputs[0] + inputs[1] exceeds K, then there is no point in checking
// inputs[0] + inputs[2] because it will also exceed K.
inputs = sortedInputs.ToArray(); // replace the array
Array.Sort(inputs);
int bestDelta = int.MaxValue;
int bestSum = 0;
List<int> opt = new List<int>();
//StringBuilder sb = new StringBuilder(); // this is used to see the indexes are being correctly generated
int[] indexes = new int[inputs.Length];
// 'n' is the current set size. Starting at set size 1, search for a solution
for (int n = 1; n <= inputs.Length; n++) {
for (int i = 0; i < n; i++) // seed the initial indexes
indexes[i] = i; // e.g. if n = 3 then indexes = 0, 1, 2
// since the inputs have been sorted, if the first sum of indexes for set size n exceeds the value of K,
// then there is no point in checking larger sets. For example, if sum of indexes [0, 1, 2] exceed K,
// then [0, 1, 2, 3] will also exceed K. Also, if [0, 2, 3] exceeds K then any set sum after it will also exceed K.
bool isFirst = true;
while (true) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += inputs[indexes[i]];
//sb.Append(indexes[i]).Append(" ");
}
//sb.AppendLine();
if (sum > K && isFirst)
break; // no point in checking more values
isFirst = false;
if (sum <= K) {
int delta = K - sum;
if (delta < bestDelta) {
opt = new List<int>();
bestDelta = delta;
bestSum = sum;
for (int i = 0; i < n; i++)
opt.Add(inputs[indexes[i]]);
if (delta == 0) // found an exact solution, no point in checking more
return new Subset(sum, opt);
}
}
int x = n - 1;
int max = inputs.Length;
bool reset = false;
while (true) {
indexes[x]++;
if (indexes[x] == max) {
if (x > 0) {
reset = true;
x--;
max--;
continue;
}
x--;
}
break;
}
if (x < 0)
break; // all combinations of set size n have been tried.
if (reset) {
isFirst = true;
for (int i = x + 1, j = indexes[x]; i < n; i++)
indexes[i] = ++j;
}
}
if (isFirst)
break;
}
return new Subset(bestSum, opt);
}
public class Subset {
public int SumTotal;
public List<int> Elements;
public Subset(int sumTotal, List<int> elements) {
this.SumTotal = sumTotal;
this.Elements = elements;
}
}