-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathElementSubsets.java
More file actions
108 lines (88 loc) · 3.08 KB
/
ElementSubsets.java
File metadata and controls
108 lines (88 loc) · 3.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
* Author: Kevin Richardson <[email protected]>
* Date: 11/7/11
* Time: 8:34 PM
*
* Given a set of n elements, this program finds the subset of elements whose sum
* comes closest to sum(all elements)/2.
*/
import java.util.Scanner;
public class ElementSubsets
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int elemCount;
int[] elements;
String[] sets;
/**
* Read in the user's desire number of elements.
*/
System.out.println("Number of elements: ");
elemCount = scanner.nextInt();
elements = new int[elemCount];
/**
* Read in the list of elements into an array.
*/
System.out.println("List of elements: ");
for (int i = 0; i < elemCount; i++)
{
elements[i] = scanner.nextInt();
}
/**
* Find our target value ( sum(elements) / 2)
*/
double targetValue = 0;
for(int number : elements)
{
targetValue += number;
}
targetValue /= 2;
/**
* Build the list of possible sets based on elements.
* While building, calculate how closely the set's sum
* will come to the targetValue.
*/
String bestSet = "";
double bestValue = Double.MAX_VALUE;
// will store a binary string to determine whether or not a given
// element resides in a set. 1 if elems[index] does, 0 if not.
sets = new String[(int)Math.pow(2, elemCount)];
for(int i = 0; i < sets.length; i++)
{
sets[i] = Integer.toBinaryString(i);
// Run from right to left to calculate the sum of the set.
// Stop summing when the beginning of the string is encountered.
// <----
// ex: 0 would represent the set NOT having elements[0] .
// ex: 10 would represent the set having elements[1] but not elements[0].
double currentValue = 0;
for(int j = sets[i].length() - 1; j >= 0; j--)
{
if(sets[i].charAt(j) == '1')
{
currentValue += elements[j];
}
}
// If the sum is closer to the targetValue than bestSum, save this set as bestSet.
if(Math.abs(targetValue - currentValue) < Math.abs(targetValue - bestValue))
{
bestSet = sets[i];
bestValue = currentValue;
}
}
/**
* Print out the bestSum as well as the set comprising it.
*/
System.out.println("Target sum: " + targetValue);
System.out.println("Closest value: " + bestValue);
System.out.print("Set: ");
for(int i = bestSet.length() - 1; i >= 0; i--)
{
if(bestSet.charAt(i) == '1')
{
System.out.print(elements[i] + " ");
}
}
}
}