Answer Happy

Fair Division of Christmas Gifts You are helping Santa Clauses to distribute gifts to children. For ease of delivery, you are asked to divide n gifts into two groups such that the weight difference of these two groups is minimized. The weight of each gift is a positive integer. Please design an algorithm to find an optimal division minimizing the value difference. The algorithm should find the minimal weight difference as well as the groupings in O(n) time, where is the total weight of these n gifts. Briefly justify the correctness of your algorithm.