I'm looking for a little direction on this homework problem. I am asked the question:
An exclusive family theater open all day has a capacity of C seats.
To use the theater, each group must make an offer. Each offer cannot be
less than a minimum amount (B) and any group can bid more than B for
increase the chances that his offer will be accepted to use the theater.
Your task is to design a dynamic programming solution that will help you
the theater director reviews the daily offerings and chooses among them
those who will maximize the daily income of theater R.
A. First, let's assess the following things that look promising
gourmet choice. Evaluate the strategy for dividing the amounts of group offers
by group size and choose the group with the largest amount per
member first. Give an example to show that this strategy does not
produce an optimal solution.
B. Write an equation which expresses the maximum income R recursively and shows the optimal substructure of this problem.
C. Draw the recursion tree from the following example. Suppose the theater capacity (C) is 15 and the minimum bid amount (B) is also $ 15
(8 more similar problems) …
Basically, my question is how is this a dynamic programming (DP) issue? We have learned the methods of stem cutting and the longest common consequences for DP and I cannot understand how it fits into one or the other. I tried both to use sample data as well as a table later on the problem, but I am stuck as to how it is a DP problem. Wouldn't you just choose the maximum bid each time? I would appreciate any direction on this.
FWIW, here's what I have for problem A. I haven't gone past it because I don't know where to start with this specific problem.
A. Let's say we have the following table:
Group 1 2 3 4
Group size 3 5 7 9
Bundle 30 25 35 36
$ / person 10 5 5 4
As we can see, group 1 has the highest $ / person at $ 10 / person, but group 4 has the highest bid and therefore the most revenue.