Problem 2 (30 points). You are given k distinct bins arranged in an ordered sequence. Your task is to throw n balls (in order) into these k bins. However, every ball has an associated weight with it. The task is set up in a way such that: You may throw a consecutive sequence of balls into the same bin. Once you move on from bin i, you cannot come back to throw later balls into it. Define the load of a bin as the total weight of all balls in it. Design and analyze an efficient DP algorithm to determine the balls contributing to the load on every bin so as to minimize the maximum load over all bins. In your solution, make sure to explicitly state: 1. the optimal substructure and why it is optimal, 2. the DP recurrence formula including base cases 3. whether your algorithm is bottom-up or top-down DP, 4. the description of vour algorithm, and 5. the time and space complexity of your algorithm For example, suppose B 20,9, 15, 10, 32 are the weights of the balls and k-3, then your algorithm should return l,-20, 9j, 12-115, 10], and 13-32, where li represents the list of balls corresponding to the load on bin i. The minimum max load is 32 for the given input B, and there are no other ways to throw the balls differently so that the minimum max load over all bins is any lower. In case of multiple optimal solutions, your algorithm may output any one of them Problem 2 (30 points). You are given k distinct bins arranged in an ordered sequence. Your task is to throw n balls (in order) into these k bins. However, every ball has an associated weight with it. The task is set up in a way such that: You may throw a consecutive sequence of balls into the same bin. Once you move on from bin i, you cannot come back to throw later balls into it. Define the load of a bin as the total weight of all balls in it. Design and analyze an efficient DP algorithm to determine the balls contributing to the load on every bin so as to minimize the maximum load over all bins. In your solution, make sure to explicitly state: 1. the optimal substructure and why it is optimal, 2. the DP recurrence formula including base cases 3. whether your algorithm is bottom-up or top-down DP, 4. the description of vour algorithm, and 5. the time and space complexity of your algorithm For example, suppose B 20,9, 15, 10, 32 are the weights of the balls and k-3, then your algorithm should return l,-20, 9j, 12-115, 10], and 13-32, where li represents the list of balls corresponding to the load on bin i. The minimum max load is 32 for the given input B, and there are no other ways to throw the balls differently so that the minimum max load over all bins is any lower. In case of multiple optimal solutions, your algorithm may output any one of them
