Programming Assignment 3

The government of CSA (Confederation of States of Algorithmia) has built a new city with n houses. These houses need to be furnished before they are allocated to people. Mr. Contractor is appointed to take care of furnishing all the n houses. Mr. Contractor knows the profit P_i that can be obtained from furnishing the i-th house. Assume that each P_i is a positive integer in the range 1...M, where M is the maximum profit that can be achieved from a single house.

Mr. Contractor wants to allocate the duty to his two sons. Suppose that his first son bags a profit S₁, and the second son bags a profit S₂. Let T = P₀ + P₁ + ... + P_n-1 be the total profit from all the houses. So T = S₁ + S₂. Mr. Contractor loves his first son twice as much as his second son (don't ask me why, it is his family matter). Therefore, he likes to ensure that S₁ is as close to 2S₂ as possible. Ideally, we should have S₁ = 2T / 3 and S₂ = T / 3, but this is not necessarily achievable, since there need not exist a subset of houses, the total profit from which is exactly 2T / 3. So Mr. Contractor plans to divide the houses to his two sons in such a way that the absolute difference |S₁ - 2S₂| is as small as possible.

Since there are 2ⁿ subsets of houses, computing the sums of profits for all these subsets leads to an exponential amount of work. Mr. Contractor uses a dynamic-programming algorithm instead. He builds a two-dimensional table A[i,j], where i runs from 0 through n-1, and j from 0 through T. The element A[i,j] stores the possibility whether a profit of j (exactly) can be achieved from a subset of Houses 0,1,2,...,i. He initializes the first row A[0,j] suitably. For i >= 1, he computes A[i,j] as follows. If A[i-1,j] stores a non-zero value, then the profit j can be achieved from Houses 0,1,2,...,i-1. If so, he stores a non-zero value in A[i,j]. Otherwise, if A[i-1,j-P_i] is a non-zero value, then by including House i the exact profit j can be achieved. In this case too, he stores a non-zero value at A[i,j]. If both the above conditions fail, there is no way to achieve the exact profit j from Houses 0,1,2,...,i, and so he sets A[i,j] to 0.

After the entire array A is prepared, Mr. Contractor looks at the last (that is, (n-1)-th) row to obtain the best partitioning of the houses to his two sons.

Write a program to implement Mr. Contractor's algorithm.

• Read the number of houses (n) and the profit bound for one house (M) from the user.
• Populate the profit array P[ ] with random integer entries in the range 1,2,...,M.
• Initialize the d-p array A (its first row).
• Use Mr. Contractor's algorithm to populate the remaining rows of A. For your future convenience, you may use two seperate non-zero values to differentiate between the two cases that make an entry in A non-zero.
• From the last row of A, decide the sums S₁ and S₂ which minimize the imbalance |S₁ - 2S₂|.
• Compute a subset (this need not be unique) of houses for the first son so that his total profit from this subset is exactly S₁. The remaining houses go to the second son. Print the lists of houses for the two sons.

Sample Output

   Enter number of houses (n) : 20
   Enter profit bound (M)     : 1000000
   Profits are 618470 562398 186275 346181 972780 668101 188523 288997 866492 711633 80067 928084 299838 852255 232332 280079 180655 525332 707770 801006 
   Profit for first son  : 6864839
   Profit for second son : 3432429
   Imbalance (S1 - 2*S2) : -19
   First son gets houses   0 2 3 4 7 8 9 11 12 14 16 17 18 
   Second son gets houses  1 5 6 10 13 15 19

Remarks

The running time of this d-p algorithm is dominated by the time to prepare the table A, and is Θ(nT), which is O(n²M). So long as M is a constant, the input size is Θ(n), and this running time is a polynomial in the input size. If we allow M too to grow, then the input size is O(n log M), and the running time is exponential in log M. However, if we choose to represent the individual profits in unary (instead of binary), the input size becomes O(nM), and the running time is polynomial in this unary input size. Such algorithms are called pseudopolynomial-time.

Mr. Contractor's problem is one of a class of NP-Complete problems (including the knapsack problem, the subset-sum problem, and the balanced-partitioning problem) that admit pseudopolynomial-time algorithms. These problems are called weakly NP-Complete. Your Algo-II course would have a discussion on these problems.

Let Mr. Contractor's sons furnish the houses. Meanwhile, the CSA government would plan for allocation of these houses to suitable families, and would be likely to face new computational problems. If needed, CSA government officials will again call for your help. Those may be future programming assignments for you.

Submission Site

---

Back | Home