Create a program that solves the following problem: Given a list of distinct int

Question

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}. You should solve this problem by brute-force: generate a collection of every possible subset of every possible size from the given list. Then check every subset in the collection and 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.

Explanation / Answer

initialize a list S to contain one element 0. for each i from 1 to N do let T be a list consisting of xi + y, for all y in S let U be the union of T and S sort U make S empty let y be the smallest element of U add y to S for each element z of U in increasing order do //trim the list by eliminating numbers close to one another //and throw out elements greater than s if y + cs/N

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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