I'm working on a dynamic programming problem and the problem requires selling a product over T time periods and maximizing the total actual sale amount. The total number of products is N and I plan to sell some products over different periods n0,n1,⋯,nT−1 and ∑ni=N. But the actual sale amount Si and sale price Pi are based on the below formulas. Assume that α=0.001 and π=0.5

1. Initialize P=0. Then for i=0,1,…,T−1
2. Compute new Pi=⌈0.5∗(Pi ni)⌉
3. At time i we sell Si = ⌈(1−αP^π)*ni⌉ products

For example, assume we already know $n_i$ for all periods, the trading will be below

    P = 0
    T = 4
    N = 10000
    alpha = 1e-3
    pi = 0.5
    S = np.zeros(T,dtype='i')
    n  = np.array([5000,1000,2000,2000])
    print(n)
    total = 0
    for i in range(T):
        P = math.ceil(0.5*(P   n[i]))
        S[i] = math.ceil((1 - alpha*P**pi)*n[i])
        total  = S[i]
        print('at time %d, M = %d and we trade %d shares' %(i,M,S[i]))
    print('total sold =', total)

Continue this process until T−1 period. For fractional numbers, choose the ceil of them for calculation. I'm trying to work on the last period initially and back to 0 period, which is the idea of dynamic programming.
For example, if T=10 and I'm selling product at the last period, I will determine P9=⌈0.5∗(P8 n9)⌉ and sell S9 = ⌈(1−αP9^π)*n9⌉ and find the maximum S9 and back until S0. During this process, we need to go through all periods T, all possible trading, for now, ni and for next period ni 1 since the sum should be a constant and all possible previous price. There are four loops in this algorithm, which is very inefficient. Is it possible to relate some variables to reduce the loop for dynamic programming? Thank you very much.

CodePudding user response：

You will not be able to apply dynamic programming to this problem, unless you're able to apply some mathematical wizardry to put some bounds on the effects of the price P.

Dynamic programming relies on the problem having the optimal substructure property. From wikipedia:

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

However, your problem does not exhibit this property- if we calculate the optimal solution for T intervals and N items, we cannot use that solution for T 1 intervals and N K items, because the price in the T 1 problem is dependent on the T interval price. A sub-solution with a higher price P (for the last interval) but suboptimal profits overall may still be used to construct the optimal profit for T 1, because of the increased price P. This prevents us from appling dynamic programming.

CodePudding user response：

Your current method has complexity O(N^T). Dynamic programming can be used to reduce this to O(T.N^3) which should be more efficient for values of T of 4 and higher.

Note that the problem has the following properties:

1. A higher price results in fewer sales
2. A higher price at a particular time results in higher prices later (if the same subsequent choices for ni are made)

This means that you can solve with dynamic programming the subproblem of what is the lowest price that can be achieved for each number of sales:

1. with exactly t time periods
2. with the ni for the t time periods summing to n

To compute this subproblem requires looping over the choices for the number in the final time period, and combining choices from previous subproblems.

Note that solving the subproblem gives an array of up to N results, where entry k in the array gives the lowest price for getting exactly k sales.

There are O(T.N) subproblems, and each subproblem requires O(N^2) to solve for a total complexity of O(T.N^3).