结合递归和循环求最大值
我试图解决一个递归练习，并感到非常困惑。问题如下：
假设我有一个n平方米的公寓，i=1，2，3…，n是平方米的单位，p1，p2，p3，…，pn是每平方米的相应价格。p1是1平方表的价格，pn是n平方表的价格)。
我想找出分配公寓的最佳方式，这样才能给我“最大的收入”。
例如，如果我有4平方米公寓，而大小为1,2,3,4的价目表相应为1,5,8,9，那么这是一组选项：
- 离开公寓作为一个4平方米单位(价值: 9)
- 将4平方米分成1,1,1,1平方米(总价值: 4)
- 将4平方米分成1,1,2平方米(总价值: 7)
- 将4平方米分成2,2平方米(总价值: 10)
- 将4平方米分成1,3平方米(总价值: 9)
因此，我的函数“利润”应该返回数字10作为输入:利润(1，5，8，9，4)
我被要求使用以下模式来解决这个问题，其中递归调用必须仅在循环中：
def profit(value, size):
...
for i in range(size):
...
return ...在很长一段时间后，我设法在没有循环条件的情况下解决了这个问题，但它确实让我感到沮丧的是，递归函数是多么的困难和不直观。我真的很感激这些问题的一般指导技巧，或者即使你能让我参考其他可能帮助我更好地学习这个话题的资料。有时候对我来说太难跟上了。
当然，如果你能帮我做这个特殊的工作.
回答 3
Stack Overflow用户
发布于 2018-07-11 07:49:10
使用以下功能解决了这个问题：
def profit(value,size):
if size <= 0:
return 0
lst1 = []
for i in range(size):
lst1.append(profit(value, size-(i+1))+value[i])
return max(lst1)Stack Overflow用户
发布于 2018-07-10 16:45:34
您可以创建一个函数，该函数可以查找平方大小范围的可能组合。然后，对于总和为4的每一个组合，都可以找到最大的地板尺寸：
def profit(value, size):
def combinations(d, _size, current = []):
if sum(current) == _size:
yield current
else:
for i in d:
if sum(current+[i]) <= _size:
yield from combinations(d, _size, current+[i])
options = list(combinations(range(1, size+1), size))
prices = dict(zip(range(1, size+1), value))
result = max(options, key=lambda x:sum(prices[i] for i in x))
return sum(prices[i] for i in result)
print(profit([1,5,8,9], 4))输出：
10Stack Overflow用户
发布于 2018-07-10 16:45:36
我不想给你一个完整的答案，因为这似乎是一个任务。然而，我将尝试把你推向正确的方向，为什么递归在这里是最优的。我在您的示例中添加了一行代码，我认为这将帮助您解决问题。在将其添加到代码中之前，我建议您尝试完全了解这里发生的事情。
def profit(value, size):
for i in range(size):
# Get the profit of the size before this combined with a 1
profit(value, size - 1) + profit(value, 1)如果你很难理解为什么这是有用的，请留下评论，我可以稍后给你一个更深入的解释。
编辑：
在实现递归函数时要记住的一个关键概念是基本案例。
在本例中，您已经知道每个大小的值是什么，因此将其合并到解决方案中。
def profit(value, size):
# BASE CASE
if size == 1 :
return value[0]
# Size > 1
for i in range(size):
# Return the maximum value of all given combinations.
return max(value[size], profit(value, size - 1) + profit(value, 1))这是一个几乎完全的解决方案，现在只缺一块。
提示:此代码当前无法测试利润(值，2) +利润(值，2) (这恰好是本场景中的最大利润)
https://stackoverflow.com/questions/51270368
复制相似问题
腾讯云开发者
