最近在研究最优化问题时，发现了这篇文章对求解过程写的比较清楚 投资分配问题_动态规划 - 你的雷哥 - 博客园 (cnblogs.com)  

以该问题为模型，写了一段 python 代码。

问题提出：

求解流程： 

针对该问题及求解思路，用 python 编写如下代码：

import numpy as np

g = np.array([
    [0, 20, 50, 65, 80, 85, 85],
    [0, 20, 40, 50, 55, 60, 65],
    [0, 25, 60, 85, 100, 110, 115],
    [0, 25, 40, 50, 60, 65, 70]
])


def opt(g):
    m = g.shape[0]  # 工厂数
    n = g.shape[1]  # 投资数
    dp = np.zeros([m, n, m])  # 各阶段最优策略
    f = np.zeros([m, n])
    f[0] = g[0]
    dp[0, :, 0] = np.arange(n)
    for k in range(1, m):
        for i in range(n):
            b = np.zeros(n)
            for j in range(i):
                b[j] = g[k, j] + f[k - 1, i - j]
            f[k, i] = np.max(b)
            dp[k, i] = dp[k - 1, i - np.argmax(b)]
            dp[k, i, k] = np.argmax(b)  # j
    return f[-1, -1], dp[m - 1, n - 1]

print(opt(g))