# Transition State for Dynamic Programming Problem

This is straight from the book: Optimization Methods in Finance.

## Overview

The question is about how the transition state works from the example provided in the book. I attempted to trace through it myself but came across a contradiction.

In Chapter 13, we come across an example similar to the Knapsack Problem. The main difference is we can make "multiple investments" in each project (instead of simple binary 1-0 choice)

We want to optimize between 4 projects with total budget of $14 (values in millions) $$Maximize \;\; 11x_1 + 8x_2 + 6x_3 + 4x_4 \\ Subject \;to \;\; 7x_1 + 5x_2 + 4x_3 + 3x_4 <= 14 \\ x_j >= 0, \; j = 1..4$$ Note that $$y_j$$ will be the cost (constraint) and $$p_j$$ will be the profit (what we want to maximize) as we proceed. The book proceeds to formulate the dynamic programming approach with four stages: $$i=1,2,3,4$$ where the fourth stage will have states $$(4,0), (4,3), (4,6), (4,9), (4,12)$$ corresponding to 0, 1, 2, 3, and 4 investments in the fourth project. The decision to be made at stage $$i$$ is the number of times one invests in the investment opportunity $$i$$. Therefore, for state $$(i,j)$$, the decision set is given by: $$S(i,j) = \{d|\frac{j}{y_i} \geq d \}$$ where d is a non-negative integer The transition state is : $$T((i, j), d) = (i + 1, j - y_i* d)$$ ## My issue and contradiction Now, let us say we have a state at stage 3: $$(i,j)$$ is $$(3,12)$$ Since investment 3 has a cost $$y_3=4$$, it means $$(3,12)$$ is a state where 4 investments are made in investment 3. Calculating our decision set: $$S(3, 12) = \{d\|\frac{12}{4} \geq d\} \\S(3,12) = \{0, 1, 2, 3\}$$ However, since we are currently at \$12, that means we should only have \\$2 left to spend.

Applying the transition function:

$$T(3,12), 0) = (4, 12 - 4*0)\\T(3,12), 0) = (4, 12)$$ How is this feasible? Also for the following:

$$T(3,12), 1) = (4, 12 - 4*1) \\T(3,12), 1) = (4,8)$$ This is a state that does not exist, since it was provided in the book that the possible states for stage 4 is $$(4, 0), (4,3), (4,6), (4,9), (4,12)$$

Pictures below for full problem:

KnapSack Problem

Decision Set and Transition