By Prem Tiwari in C++ Tutorial. Updated on
In this program, we are going to share a C++ Program for Tug of War with the output. If you are a beginner and want to start learning the C++ programming, then keep your close attention in this tutorial as I am going to share a program for C++ Program for Tug of War with the output.
Copy the below C++ program and execute it with the help of GCC compiler. At the end of this program, We have shared the output of this program.
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 | #include <iostream> #include <stdlib.h> #include <limits.h> using namespace std; // function that tries every possible solution by calling itself recursively void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements, bool* soln, int* min_diff, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return; // checks that the numbers of elements left are not less than the // number of elements required to form the solution if ((n/2 - no_of_selected_elements) > (n - curr_position)) return; // consider the cases when current element is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true; // checks if a solution is formed if (no_of_selected_elements == n/2) { // checks if the solution formed is better than the best solution so far if (abs(sum/2 - curr_sum) < *min_diff) { *min_diff = abs(sum/2 - curr_sum); for (int i = 0; i<n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); } // removes current element before returning to the caller of this function curr_elements[curr_position] = false; } // main function that generate an arr void tugOfWar(int *arr, int n) { // the boolen array that contains the inclusion and exclusion of an element // in current set. The number excluded automatically form the other set bool* curr_elements = new bool[n]; // The inclusion/exclusion array for final solution bool* soln = new bool[n]; int min_diff = INT_MAX; int sum = 0; for (int i=0; i<n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false; } // Find the solution using recursive function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0); // Print the solution cout << "The first subset is: "; for (int i=0; i<n; i++) { if (soln[i] == true) cout << arr[i] << " "; } cout << "\nThe second subset is: "; for (int i=0; i<n; i++) { if (soln[i] == false) cout << arr[i] << " "; } } int main() { int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; int n = sizeof(arr)/sizeof(arr[0]); tugOfWar(arr, n); return 0; } |
The first subset is: 45 -34 12 98 -1
The second subset is: 23 0 -99 4 189 4
Sharing is caring!
