In Java, how should I find the closest (or equal) possible sum of an Array's elements to a particular value K?
For example, for the array {19,23,41,5,40,36} and K=44, the closest possible sum is 23+19=42. I've been struggling on this for hours; I know almost nothing about dynamic programming. By the way, the array contains only positive numbers.
You would typically use dynamic programming for such a problem. However, that essentially boils down to keeping a set of possible sums and adding the input values one by one, as in the following code, and has the same asymptotic running time: O(n K), where n is the size of your input array and K is the target value.
The constants in the version below are probably bigger, however, but I think the code is much easier to follow, than the dynamic programming version would be.
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);
}
}
EDIT
A short note on running time might be useful, since I just claimed O(n K) without justification.
Clearly, initialization and printing the result just takes constant time, so we should analyse the double loop.
The outer loop runs over all inputs, so it's body is executed n times.
The inner loop runs over all sums so far, which could be an exponential number in theory. However, we use an upper bound of K, so all values in sums are in the range [0, K]. Since sums is a set, it contains at most K+1 elements.
All computations inside the inner loop take constant time, so the total loop takes O(K). The set newSums also contains at most K+1 elements, for the same reason, so the addAll in the end takes O(K) as well.
Wrapping up: the outer loop is executed n times. The loop body takes O(K). Therefore, the algorithm runs in O(n K).
EDIT 2
Upon request on how to also find the elements that lead to the optimal sum:
Instead of keeping track of a single integer - the sum of the sublist - you should also keep track of the sublist itself. This is relatively straightforward if you create a new type (no getters/setters to keep the example concise):
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;
}
}
The initialization now becomes:
SubList opt = new SubList();
Set<SubList> sums = new HashSet<>();
sums.add(opt);
The inner loop over the sums needs some small adaptations as well:
for (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);
}
You can see it as a n-choose-k problem for all possible k so the complexity is exponential.
K. The set should include i numbers, for i=1; i<=N; i++. To implement this, for each i just take all the n-choose-i combinations of the numbers in the array.finalResult variable with the best set of numbers found so far and their sum.finalResult and update it if necessary.It reminds me of the Knapsack problem, so you may want to take a look at it.
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;
}
I would say first sort the array. Then your example would be: arr = {5, 19, 23, 36, 40, 41}. Then: 1) Take arr[0] and arr[i], where i = arr.Size. Sum it and record the difference between the sum and K, if the sum is lower than K. 2) If sum > K, do step 1, but instead of arr[i], use arr[i-1], because we want to lower our sum. If sum < 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.
----------------Edited for arbitrary number of elements in the solution----------------
I believe you may need a tree. Here's what I'm thinking:
1) Choose a number as your top node.
2) For each number in the set, create a child node, and for each branch that was created, calculate the sum of that branch.
3) If the sum is less then K, we branch again, creating child nodes for all the elements in the set. If the sum is greater than K, we stop, keep the difference between the sum and K(If sum < K). If we find a branch with a better sum, then we keep that branch. Repeat this process until all branches are done branching.
Do steps 1-3 with different topnodes.
