(java) Create a program that solves the following problem: Given a list of disti

Question

(java) Create a program that solves the following problem: Given a list of distinct integers and a target integer, determine the largest sum less than or equal to the target value that can be created from a subset of those integers. List the sum and all the subsets that add up to that sum. For example, if the list of integers is {1, 2, 5, 6} and a target value is 6, the largest sum that is less than or equal to the target value of 6 is 6, and that sum can be created by the subsets {1, 5} and {6}. Here is another example: if the list of numbers is {1, 2, 3, 4, 5} and the target is 3, then the largest sum that is less than or equal to 3 that can be created from the list of integers is 3. This sum can be created with {3} and with {2, 1}. If the list of numbers is {1, 2, 3, 4, 5} and the target is 2, then the largest sum is 2, which can be created with {2}.If the list of numbers is {3, 4, 6} and the target value 7, then there is one subset that gives the target value, {3, 4}. If the list of numbers is {1, 2, 3, 4, 5} and the target value is 100, then the largest sum less than or equal to 100 is 15, which can be created with the subset {1, 2, 3, 4, 5}. Generate every possible subset of every possible size from the given list and check every subset to find the subsets that have a sum closest to and less than or equal to the target value. To save some time while you are testing, your program should use a default number list: {1, 2, 4, 5, 8, 12, 15, 21}. When you start the program it should ask if you want to use the default list. If you answer no, then you are prompted to enter the number list. In either case, you should enter a target value each time you run the program. Include javadoc comments.

Explanation / Answer

import java.util.Stack;

public class GetAllSubsetByStack {
public static final int TARGET_SUM = 15;
private Stack<Integer> stack = new Stack<Integer>();
private int sumInStack = 0;
public void populateSubset(int[] data, int fromIndex, int endIndex) {

if (sumInStack == TARGET_SUM) {
print(stack);
}

for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

if (sumInStack + data[currentIndex] <= TARGET_SUM) {
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];
populateSubset(data, currentIndex + 1, endIndex);
sumInStack -= (Integer) stack.pop();
}
}
}

private void print(Stack<Integer> stack) {
StringBuilder sb = new StringBuilder();
sb.append(TARGET_SUM).append(" = ");
for (Integer i : stack) {
sb.append(i).append("+");
}
System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
}
}

//main class is here.

public class Main {

private static final int[] DATA = { 1,6,3, 4, 5, 2, 7, 8, 9, 10, 11, 13,
14, 15 };

public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}

Note: Hope this programs helps you. If you want to give the value at run time you can also give that value using the

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.