The multiple-choice knapsack problem is an extension of the the knapsack problem where you have several variants of an item that you may select to include in the knapsack. For example, if we think about filling a shopping cart full of groceries, consider the item Milk. We may choose to include a quart of milk, a gallon of milk, or not select any Milk at all. In the multiple-choice knapsack problem, we are given the capacity C of the knapsack and a collection of items i = 1, . . . , n. For each item i, we are given a selection of variants of the item j = 1, . . . , L_i . Associated with the j?th variant of item i is a value, v_ij , and a size s_ij . We will assume that variant L_i of item i is the option of not including any variant of item i in the knapsack, i.e., v_iL_i = s_i L_i= 0. The goal of the problem is to select exactly one variant of each item to maximize the value of the knapsack such that the weight of the selected variants does not exceed the capacity of the knapsack. Note that selecting the `i-th item for every item i is a feasible solution to this problem. We will denote the maximum number of variants of an item as L = max_i L_i.

Develop a dynamic programming algorithm for the multiple-choice knapsack problem. You do not need to provide the pseudocode for the algorithm. Provide the state defininitions, the recurrence relationships between the states of your problem, the base case for the recurrence, and determine the time required to solve the dynamic program (i.e., how long will it require to calculate the value functions for all states in our dynamic program.) Hint: you can have the states of the dynamic program be the same for the multiple-choice knapsack problem as for the knapsack problem itself.