$11$

$7.[$Dynamic Programming $2](16$ points$)$

Suppose you are running a bus tour company with a double$-$decker bus. The upper deck has $U$ seats and the lower deck has $L$ seats. There are $n$ groups of people $(p_1,v_1),$dots,$(p_n,v_n)$ where $p_i$ is the number of people in the group i and $v_i$ is how much the group will pay to take the tour. If you decide to take a group then they all must fit on the upper deck or the lower deck, you cannot split up the group. You only have a limited number of seats so you may not be able to accommodate all $n$ groups so you wish to find a subset of the groups that you can fit on the tour that maximizes to the total value.

Design a DP algorithm that returns the maximum total value.

Step $1$: Description of subproblems

Let $B[i,j,k]$ be the maximum value you can achieve considering groups $1,$dots,$k$ such that that bus has i available seats in the upper deck and $j$ available seats in the lower deck.

Step $2$: Base Case$($s$)(2$ points$)$

Step $3$: Recursion $($with justification or case analysis$)(8$ points$)$

Step $4$: ordering $(2$ point$)$

Step $5$: form of output $(2$ point$)$

Step $6$: runtime analysis $(2$ points$)$