Python动态规划实现：肥料资源最优分配求解树木成熟最大概率

假设农场共有n棵圣诞树，目标是最大化所有树木在圣诞节前成熟的概率。现有m袋肥料可用于加速树木生长，肥料袋不可拆分，每袋肥料仅能施用于一棵树木。
我们已预先统计得到列表p[i][j]，其代表给第i棵树施用j袋肥料时，该树按时成熟的概率。注意：更多肥料不一定会提升树木生长速度，因此概率随施肥量增加可能上升也可能下降。
需要求解的核心目标：找到最优肥料分配方案，得到所有树木都按时成熟的最大概率。

请使用动态规划填表法解决该问题，编写函数best_allocation(number_of_trees, number_of_bags, probability_list)，传入三个参数分别为树木总数、肥料总袋数、各树对应不同施肥量的成熟概率列表，函数返回最优分配方案下所有树木按时成熟的最大概率值。

probs = [[0.5, 0.5, 1],[0.25,0.1,0.75]]
best_allocation(2,2,probs)
# 该场景下最优方案为给第0棵树施0袋肥，第1棵树施2袋肥，总概率为0.75*0.5 = 0.375

probs = [[0.5, 0.75, 0.25],[0.75,0.25,0.8]]
best_allocation(2,2,probs)
# 该场景下最优方案为给第0棵树施1袋肥，第1棵树施0袋肥，总概率为0.75*0.75=0.5625

思路 #

我们采用动态规划填表法求解：

• 定义dp[i][k]为前i棵树总共使用k袋肥料时，所有前i棵树都按时成熟的最大概率
• 初始状态：dp[0][0] = 1（0棵树用0袋肥，成熟概率为1），其余初始状态为0
• 状态转移：对每棵树i，枚举给这棵树分配的肥料袋数j，再枚举前i棵树总共用的肥料袋数k，更新状态为dp[i+1][k] = max(dp[i+1][k], dp[i][k-j] * probability_list[i][j])
• 最终结果为dp[number_of_trees][number_of_bags]

代码实现 #

def best_allocation(number_of_trees, number_of_bags, probability_list):
    # 初始化dp数组
    dp = [[0.0] * (number_of_bags + 1) for _ in range(number_of_trees + 1)]
    dp[0][0] = 1.0
    
    for i in range(number_of_trees):
        # 遍历前i棵树使用k袋肥的所有情况
        for k in range(number_of_bags + 1):
            if dp[i][k] == 0:
                continue
            # 枚举给第i棵树分配的肥料袋数j，不能超过剩余可用量和该树的最大统计施肥量
            max_j = min(number_of_bags - k, len(probability_list[i]) - 1)
            for j in range(max_j + 1):
                current_prob = dp[i][k] * probability_list[i][j]
                if current_prob > dp[i+1][k + j]:
                    dp[i+1][k + j] = current_prob
    return dp[number_of_trees][number_of_bags]

内容的提问来源于stack exchange，提问作者Ning