The "equal piles" problem is this: Given a large collection of numbers, sort them into two piles, such that the sum of the numbers in the first pile equals the sum of the numbers in the second pile. Equivalently, find a subset of the numbers whose sum is half the total sum. This problem is NP-complete, so there is no known solution that takes less than exponential time.
This assignment will use multiple agents to search for a solution. There are probably more efficient ways to tackle this problem, but the intent here is to use the problem to teach STM.
Create a vector of N random numbers, each in the range 1 to M. (Probably good values are N=50, M = 1000000.) You can, if you like, ensure that the sum of all the numbers is even.
Print the total, and half the total, properly labeled. Half the total is your "goal number."Take about half the numbers, for example the first N/2 numbers, and call this the "current best solution." Print this solution--that is, print the numbers in the solution, the total of those numbers, and the difference between that total and the goal number.
Create 100 agents, with id numbers 1 to 100, giving each agent a copy of the current best solution. Each agent also needs access to all N numbers and to the goal number, but these won't be changed and don't need to be copies.
Each agent should:
Note that the agents themselves do no printing; all printing is done from the "main" thread.
Stop the program when about 1000 improvements have been made, or when an exact solution is found. Print the best solution.
Your program is due before 6am Friday, October 9, via Canvas.