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树，那么查看所有可能的包分配到"new";树(+ 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):
...