时间戳

首页 > 解决方案 > 递归地尝试找到最大的 w/o 循环

python - 递归地尝试找到最大的 w/o 循环

问题描述

所以我得到了一个这种格式的有序对元组：

(x,y)其中x代表物体的物理重量，y代表物体的成本/价值。

((5, 20), (10, 70), (40, 200), (20, 80), (10, 100))

对象只能使用一次，但在有序对的原始元组中可能有多个对象。

z 是可以运输的最大重量。它是一个整数。z 可能是 50 或类似的值。

目标：在给定限制 Z 的情况下，找到您可以发送的最大值。

困难在于我们只能使用递归，不能使用循环，也不能使用 python 内置函数。

我试图在一个整数列表中计算出最大值，我分别做了这个以试图获得某种想法。我也尝试过给物体一个“质量”并做价值/重量，但这也不是很好。

def maximum_val(objects: ((int,int),) , max_weight : int) -> int:
    if max_weight == 0:
        return 0
    else:
        return objects[0][1] + maximum_val(objects[1:], max_weight - gifts[0][0])

((5, 20), (10, 70), (40, 200), (20, 80), (10, 100))

示例：给定上面的元组和限制Z=40，可以获得的最佳值是250 -> (10, 70), (10, 100), (20, 80)

标签： pythonrecursionpython-3.7

解决方案

这被称为背包，您正在寻找递归变体。
在每一步，检查什么是最好的。包括第一个对象或跳过第一个对象：

对象 = ((5, 20), (10, 70), (40, 200), (20, 80), (10, 100))

def recursive_knapsack(objects, limit ):

    if not objects:
        return 0

    if objects[0][0] > limit:
        #first object cant fit
        return recursive_knapsack(objects[1:],limit)

    include =  objects[0][1] + recursive_knapsack(objects[1:], limit-objects[0][0])
    exclude = recursive_knapsack(objects[1:],limit)

    if include < exclude:
        return exclude
    else:
        return include

推荐阅读