Python资源分配中的动态规划

Question

问题描述：

假设农场上有n棵圣诞树。你想最大限度地利用所有树木都准备好迎接圣诞节的机会。为了使树木生长得更快，你可以用m袋肥料喂养它们。

你已经计算了每棵树按时准备好的概率，这是基于你在树上施用的肥料袋数。你有一个列表p[i][j]表示如果施用j袋肥料，植物i将准备好的概率。你不能把袋子分开，一旦一袋肥料施到一棵树上，你就不能把它用在不同的树上。

施肥越多，树木的生长速度并不总是越快，因此，随着施肥量的增加，这种可能性可能会降低或增加

找出所有树木在圣诞节前完全生长的最大可能性

问题：
如何用动态规划表格法求解？请编写一个包含3个参数的函数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)
#In this case, the best choice is to allocate 0 bags to tree0, and allocate 2 bags to tree1, 
#which gives us an overall probability of 0.75*0.5 = 0.375

probs = [[0.5, 0.75, 0.25],[0.75,0.25,0.8]]
best_allocation(2,2,probs)
#In this case, the best choice is to allocate 1 bags to plant0, and allocate 0 bags to plant1. 
#The overall probability is 0.75*0.75=0.5625

Answer 1

您正在寻找一个递归函数，如：

def best_allocation(number_of_trees, number_of_bags, probability_list):
    if number_of_trees == 1:
        return max(probability_list[0][:number_of_bags + 1])
    return max(
        best_allocation(
            number_of_trees - 1,
            number_of_bags - bags,
            probability_list[1:]
        ) * probability_list[0][bags]
        for bags in range(0, number_of_bags + 1)
    )

如果您只有一棵树，则采用可用的最大概率（限制是可用行李的数量）。如果您有n + 1树，则查看所有可能的行李分配到“新”树（+ 1）以及剩余行李到n树的最佳分配，然后获得最佳总体结果（max）

编辑： 向其中添加备忘录的简单方法是：

def memo(func):
    cache = {}
    def wrapper(n, m, list_of_lists):
        args = (n, m) + tuple(tuple(list_) for list_ in list_of_lists)
        if args not in cache:
            cache[args] = func(n, m, list_of_lists)
        return cache[args]
    
    return wrapper

@memo
def best_allocation(number_of_trees, number_of_bags, probability_list):
    ...