Question 1 (Knapsack, 30 points). Consider the knapsack problem where you are allowed to take items
more than once, have a total capacity of 10 and have the following items available:
Item Weight Value
A 2 4
B 3 5
C 4 9
D 5 10
E 7 16
What is the best combination of items to take?
1
Question 2 (Business Plan I, 35 points). Harold is starting a new business. He begins with $0 in capital
and wants it to be worth as much as possible at the end of n weeks, at which point he plans to sell. In
order to get there, he has k different strategies he can use to make money. Each strategy takes one week
to implement, and can be used multiple times as needed. If Harold has x dollars at the start of a week and
implements the ith strategy that week, he will have fi(x) dollars at the end of that week for some increasing
function fi (meaning that fi(x) ≥ fi(y) whenever x ≥ y).
Harold has a simple plan for determining which strategies to use in which order. Each week he will note
the number of dollars, x, that he has at the start of the week, and implement the plan with fi(x) as large as
possible. Prove that this strategy gets Harold as much money as possible by the end of the nth week.
2
Question 3 (Business Plan II, 35 points). The setup of this problem is similar to that in question 2. Please
read that question first.
Harold later realizes that things are not quite as predictable as he had previously thought. He determines
that implementing plan i in a given week has a probability pi,j of earning him j dollars (adding j to his
current amount of money) over the course of that week for each integer j between 0 and m. Harold starts
with 0 dollars and his goal is to maximize the probability that he will have at least m dollars at the end of n
weeks.
Give an algorithm that given n,m and all of the pi,j computes the maximum possible probability with
which Harold can achieve this goal. For full credit, your algorithm should run in time O(nm2k) where k is
the number of possible strategies available.
3