Dynamic programming

Suppose you have 8K to invest and there are 3 investment options available. You must investment in multiples of 1K. If x dollars are invested in investment i then you receive a profit of Pi(x) as shown in the table below.

x 0 1 2 3 4 5 6 7 8
P1(x) 0 5 15 40 80 90 95 98 100
P2(x) 0 5 15 40 60 70 73 74 75
P3(x) 0 4 26 40 45 50 51 52 53

What is the maximum profit you can make? How to invest $8K for maximum profit? Solve this problem with dynamic programming.

Ans:

Assuming that dp[i] is used to represent the maximum profit that i1000 yuan can obtain from investment, then dp[0]=0; dp[1]=max(pi(1)) i=1,2,3.At this time, dp[2]=max (dp[1]+dp[1], max (pi (2)), so RMB 2000 can only be invested twice in RMB 1000, or RMB 2000 can be invested once. By analogy, we can know that dp[3]=max (dp[2]+dp[1], max (pi(3)), and then deduce the transfer equation as dp[n]=max (dp[n-1]+dp[1], max (pi(n)).Under the condition of ensuring that (n-1) 1000 can obtain the maximum profit, if you want to obtain the maximum investment profit for n1000, you only need to invest in the previous way and make a new investment with the excess 1000 yuan, or invest all n1000 in the new investment, and the larger value of the two is enough, as shown in the transfer equation.

dp[0] = 0 invest null

dp[1] = 5 invest p1 1k

dp[2] = max(2 * 5, 26) = 26 invest p3 2k

dp[3] = max(26 + 5, 40) = 40 invest p1 3k

dp[4] = max(40 + 5, 80) = 80 invest p1 4k

dp[5] = max(80 + 5, 90) = 90 invest p1 5k

dp[6] = max(90 + 5, 95) = 95 invest p1 5k + p1 1k

dp[7] = max(95 + 5, 98) = 100 invest p1 5k + p1 1k + p1 1k

dp[8] = max(100 + 5, 100) = 105 invest p1 5k + p1 1k + p1 1k + p1 1k