CSC148 - Lab 5
Balanced Scales
Download balanced_scale.py.
You have a collection of heavy weights. The list weights gives the weight, in grams, of each of your weights. You want to know if it is possible to place all your weights on a standard balance scale such that it is balanced. Stated another way, you want to know if you can divide your collection into exactly two sets, both of which have the same total weight.
For example, take the list of weights [1,1,2,3,5,8]. We can partition this into two sets [1,1,3,5] and [2,8] such that both partitions have weight 10.
There are several ways to approach this problem.
One way is to observe that it is possible if and only if there is a subset of weights which adds up to exactly half of the total weight (sum of all the weights). So you could write a recursive method achieve_goal(weights, goal) which would return true if and only if there were some subset of weights that add up to goal.
Develop a recurrence for the achieve_goal method which works by consider an appropriate base case (weights only contains one element? weights is the empty list? something else?) and then makes two recursive calls which representing making the binary choice of either using weights[0] in your solution or not.
Another solution could involve building the two sets simultaneously, noting that weights[0] must go in one of the two partitions, and checking that the sum of the two partitions both total the same weight when you have run out of weights.
Try implementing both of these solutions for this problem, and come up with some test cases to check that they work.