假设我们有两个长度相同的列表,它们称为权重和值,并且我们还有另一个值容量。这里weights [i]和values [i]代表第i个项目的权重和值。如果我们最多可以使用容量权重,并且每个项目可以复制任意数量的副本,则必须找到可以获取的最大值。
因此,如果输入就像权重= [1、2、3],值= [1、5、3],容量= 5,那么输出将为11
为了解决这个问题,我们将遵循以下步骤-
定义一个功能dp()
。这需要我,k
如果我与重量的大小相同,则
返回0
ans:= dp(i + 1,k)
如果k> = weights [i],则
ans:= ans和dp(i,k-weights [i])+ values [i]的最大值
返回ans
从主要方法中执行以下操作-
返回dp(0,容量)
让我们看下面的实现以更好地理解-
class Solution: def solve(self, weights, values, capacity): def dp(i, k): if i == len(weights): return 0 ans = dp(i + 1, k) if k >= weights[i]: ans = max(ans, dp(i, k - weights[i]) + values[i]) return ans return dp(0, capacity) ob = Solution()weights = [1, 2, 3] values = [1, 5, 3] capacity = 5 print(ob.solve(weights, values, capacity))
[1, 2, 3], [1,5,3], 5
输出结果
11