Backtracking: Solve the Sum of Subsets Problem

Implement Algorithm 5.4 in your text

Algorithm 5.4 assumes the input data is sorted. You may assume that the input is sorted.

You must eliminate the global variables assumed in the Algorithm 5.4

1. Add parameters weight, total, W and w[] to the promising function
2. Add a global variable, the only global variable allowed, to count the number of times promising is called
3. Add parameters W, include[], and w[] to sum_of_subsets
4. Obviously cout include[1] through include[i]; must be replaced with a loop. You should also print a statement that a solution was found.

main

Main will read the data from the file for the instance of the sum-of-subsets problem. You may assume all of the data in the file is valid integer data and it contains n weights. You can assume the data is sorted. You must check for an empty file.

Contents of the file:

• n
• W
• w1 through wn

1. Prompt the user for the name of the file, echo the file name, and open the file.
2. Use assert to ensure the file opened.
3. Read n from the file, echo n, and declare include[] and w[] based on n.
4. Read the remainder of the data in from the file. main should print all of the data read.
5. Initialize total and include[n].
6. Print a message calling sum_of_subsets along with the parameter list.
7. Print the number of promising calculations.

Grade

• 90% Your correct, well documented code.
• 10% Run your program MANY times with different input. You must vary n and the number of solutions. Write a report that discusses the number of promising calculations with the analysis presented in your text.

Submission

Use turnin to submit your program. Select sumofsubsets. Your filename should be ss.cpp.
turnin output.
Last Modified 8:41 PM 6/27/2021