1.4.1 Problem B1, Hatching a Plan The aliens want to carry as few eggs as possible on their trip as they don't have a lot of space on their ships. They have taken detailed notes on the weights of all the eggs that geese can lay in a given flock and how much weight their ships can hold. Implement a dynamic programming algorithm to find the minimum number of eggs needed to make a given weight for a certain ship in dp_make_weight. The result should be an integer representing the minimum number of eggs from the given flock of geese needed to make the given weight. Your algorithm does not need to return what the weight of the eggs are, just the minimum number of eggs. Your solution must use dynamic programming Notes: If you try using a brute force algorithm on this problem, it will take a substantially long time to generate the correct output if there are a large number of egg weights available. The memo parameter in dp_make_weight is optional. You may or may not need to usethis parameter depending on your implementation Assumptions: . All the eggs weights are unique between different geese, but a given goose will always lay the same size egg The aliens can wait around for the geese to lay as many eggs as they need. Example: Suppose the first ship can carry 99 kilos and uses the first flock of geese they find, which contains geese that lay eggs of weights 1,5, 10, and 20 kilos. Your dynamic programming algorithm should return 10 (the minimum number of egg needed to make 99 kilos is 4 eggs of 20 kilos, 1 egg of 10 kilos, 1 egg of 5 kilos, and 4 eggs of 1 kilo). Hints: Dynamic programming involves breaking a larger problem into smaller, simpler subprob lems, solving the subproblems, and storing their solutions. What are the subproblems in this case? What values do you want to store? This problem is analogous to the knapsack problem, which we looked at in lectures, Imagine Hints: Dynamic programming involves breaking a larger problem into smaller, simpler subprob- lems, solving the subproblems, and storing their solutions. What are the subproblems in this case? What values do you want to store? . This problem is analogous to the knapsack problem, which we looked at in lectures, Imagine the eggs are items you are packing. What is the objective function? What is the weight limit in this case? What are the values of each item? What is the weight of each item? In [ ]: def dp_make_weight(egg_weights, target_weight, memo - ()): Find number of eggs to bring back, using the smallest number of eggs. Assumes ther an infinite supply of eggs of each weight, and there is always a egy of value 1. Parameters: egg_weights - tuple of integers, available egg weights sorted from smallest to lar target weight - int, amount of weight we want to find eggs to fit memo- dictionary, OPTIONAL parameter for memoization (you may not need to use the Returns int, smallest number of eggs needed to make target weight 7 1 #TODO: Your code here pass 1.4.2 Problem B2: Writeup Answer the following questions in the same PDF file ps2_answers.pdf. 1. Explain why it would be difficult to use a brute force algorithm to solve this problem if there were 30 different egg weights. You do not need to implement a brute force algorithm in order to answer this 2. If you were to implement a greedy algorithm for finding the minimum number of eggs needed, what would the objective function be? What would the constraints be? What strat- egy would your greedy algorithm follow to pick which coins to take? You do not need to implement a greedy algorithm in order to answer this 3. Will a greedy algorithm always return the optimal solution to this problem? Explain why it is optimal or give an example of when it will not return the optimal solution. Again, you do not need to implement a greedy algorithm in order to answer this