15-10 Planning an investment strategy

Your knowledge of algorithms helps you obtain an exciting job with the Acme Computer Company, along with a $\$10,000$ signing bonus. You decide to invest this money with the goal of maximizing your return at the end of 10 years. You decide to use the Amalgamated Investment Company to manage your investments. Amalgamated Investments requires you to observe the following rules. It offers $n$ different investments, numbered $1$ through $n$. In each year $j$, investment $i$ provides a return rate of $r_{ij}$ . In other words, if you invest $d$ dollars in investment $i$ in year $j$, then at the end of year $j$ , you have $dr_{ij}$ dollars. The return rates are guaranteed, that is, you are given all the return rates for the next 10 years for each investment. You make investment decisions only once per year. At the end of each year, you can leave the money made in the previous year in the same investments, or you can shift money to other investments, by either shifting money between existing investments or moving money to a new investement. If you do not move your money between two consecutive years, you pay a fee of $f_1$ dollars, whereas if you switch your money, you pay a fee of $f_2$ dollars, where $f_2 > f_1$.

a. The problem, as stated, allows you to invest your money inmultiple investments in each year. Prove that there exists an optimal investment strategy that, in each year, puts all the money into a single investment. (Recall that an optimal investment strategy maximizes the amount of money after 10 years and is not concerned with any other objectives, such as minimizing risk.)

b. Prove that the problem of planning your optimal investment strategy exhibits optimal substructure.

c. Design an algorithm that plans your optimal investment strategy. What is the running time of your algorithm?

d. Suppose that Amalgamated Investments imposed the additional restriction that, at any point, you can have no more than $\$15,000$ in any one investment. Show that the problem of maximizing your income at the end of 10 years no longer exhibits optimal substructure.

a. Without loss of generality, suppose that there exists an optimal solution $S$ which involves investing $d_1$ dollars into investment $k$ and $d_2$ dollars into investement $m$ in year $1$. Further, suppose in this optimal solution, you don't move your money for the first $j$ years. If $r_{k1} + r_{k2} + \ldots + r_{kj} > r_{m1} +r_{m2} + \ldots + r_{mj}$ then we can perform the usual cut-and-paste maneuver and instead invest $d_1 + d_2$ dollars into investment $k$ for $j$ years. Keeping all other investments the same, this results in a strategy which is at least as profitable as $S$, but has reduced the number of different investments in a given span of years by $1$. Continuing in this way, we can reduce the optimal strategy to consist of only a single investment each year.

b. If a particular investment strategy is the year-one-plan for a optimal investment strategy, then we must solve two kinds of optimal suproblem: either we maintain the strategy for an additional year, not incurring the moneymoving fee, or we move the money, which amounts to solving the problem where we ignore all information from year $1$. Thus, the problem exhibits optimal substructure.

c. The algorithm works as follows: We build tables $I$ and $R$ of size $10$ such that $I[i]$ tells which investment should be made (with all money) in year $i$, and $R[i]$ gives the total return on the investment strategy in years $i$ through $10$.

C++
INVEST(d, n)
    let I[1..10] and R[1..10] be new tables
    for k = 10 downto 1
        q = 1
        for i = 1 to n
            if r[i, k] > r[q, k]   // i now holds the investment which looks best for a given year
                q = i
        if R[k + 1] + dr_{I[k + 1]k} - f[1] > R[k + 1] +  dr[q, k] - f[2]  // If revenue is greater when money is not moved
            R[k] = R[k + 1] + dr_{I[k + 1]k} - f[1]
            I[k] = I[k + 1]
        else
            R[k] = R[k + 1] + dr[q, k] - f[2]
            I[k] = q
    return I as an optimal stategy with return R[1]

d. The previous investment strategy was independent of the amount of money you started with. When there is a cap on the amount you can invest, the amount you have to invest in the next year becomes relevant. If we know the year-one-strategy of an optimal investment, and we know that we need to move money after the first year, we're left with the problem of investing a different initial amount of money, so we'd have to solve a subproblem for every possible initial amount of money. Since there is no bound on the returns, there's also no bound on the number of subproblems we need to solve.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用