Homework answers / question archive / In an imaginary country called ”The Alliance Kingdom,” multiple political parties fight to gain seats in the country’s parliament

In an imaginary country called ”The Alliance Kingdom,” multiple political parties fight to gain seats in the country’s parliament

Computer Science

Share With

In an imaginary country called ”The Alliance Kingdom,” multiple political parties fight to gain seats in the country’s parliament. Each political party must
win a minimum of electoral votes from the various states comprising Alliance
Kingdom to be able to enter the parliament. State’s electoral votes depend on
their population, so the state of ”Winter Spring” with 2 million citizens has
less electoral votes compared to ”Ashenvale” with 6 million citizens (just like
USA electoral college). In order to win a state’s electoral votes, political parties
should spend a lot of money on advertising and organizing rallies. Most parties
look for a minimum number of states to focus their money and effort on in order
to win the minimum votes required for entering the parliament.
You work for a consulting firm which specializes in helping political parties target specific states and secure required votes. Your job is to write a program
that helps a political party to win required votes.
If you think about it, this problem is very similar to subset sum problem, which
we discussed in the class, with more requirements. In the subset sum problem,
you were given an array of integers A = {a0, a1, ...., an} and a target value T
and your task was to decide if there exists a subset in the given array where the
sum of subset elements would add up to T.
For this project you have to solve the subset sum problem with more conditions.
First of all, just stating whether we have a matching subset is not enough, you
are required to count all distinct subsets that yield the subset sum. You should
also find the size of the minimum subset and count the number of distinct subsets that yield subset sum and have the minimum size.
In the Alliance Kingdom, almost every political party has a stronghold state,
which means you will get different values for T depending on the political party
you are consulting. Furthermore, all parties prefer to minimize their expenses,
which means they want to find minimum number of states as focus for their
advertisement. For every client, you will need to report every distinct subset of
states that will get them to the minimum requirement, size of smallest subset,
and every distinct subset of minimum size