备忘录算法python
时间: 2023-11-25 09:49:54 浏览: 39
备忘录算法(Memoization)是一种优化技术,它通过存储已经计算过的结果来避免重复计算。在Python中,可以使用装饰器来实现备忘录算法。下面是一个备忘录算法的例子:
```python
import functools
@functools.lru_cache(maxsize=None)
def fibonacci(n):
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)
```
在这个例子中,我们定义了一个名为fibonacci的函数,它接受一个整数n作为参数,并返回斐波那契数列的第n项。使用functools.lru_cache装饰器,我们可以将函数的结果缓存起来,避免重复计算。maxsize=None表示缓存可以无限大。
相关问题
python备忘录算法解决01背包问题
01背包问题是经典的动态规划问题,其主要思想是利用递推的方式,将问题分解为子问题来求解。
假设有n个物品,每个物品有一个重量w[i]和一个价值v[i],现在有一个容量为C的背包,问如何选择物品能够使得背包中的总价值最大。
下面是Python代码实现:
```python
def knapsack(C, w, v):
n = len(w)
# 初始化状态矩阵
dp = [[0 for _ in range(C+1)] for _ in range(n+1)]
# 递推计算状态矩阵
for i in range(1, n+1):
for j in range(1, C+1):
if j < w[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
# 返回最优解
return dp[n][C]
```
其中,状态矩阵dp[i][j]表示在前i个物品中,容量为j的背包中所能得到的最大价值。
时间复杂度为O(nC),空间复杂度为O(nC)。
备忘录求解背包问题python
以下是一个用 Python 解决背包问题的备忘录算法实现。假设有一个物品列表 `items` 和对应的价值列表 `values`,以及背包的容量 `capacity`。
```python
def knapsack_memo(items, values, capacity):
n = len(items)
memo = [[-1 for _ in range(capacity + 1)] for _ in range(n + 1)]
# 将所有的初始值设为 -1
def dp(i, j):
if memo[i][j] != -1:
return memo[i][j]
if i == 0 or j == 0:
res = 0
elif items[i - 1] > j:
res = dp(i - 1, j)
else:
res = max(dp(i - 1, j), dp(i - 1, j - items[i - 1]) + values[i - 1])
memo[i][j] = res
return res
return dp(n, capacity)
```
在上面的代码中,我们定义了一个 `memo` 数组,用于保存子问题的最优解。在递归函数 `dp` 中,我们先检查 `memo[i][j]` 是否已经计算过,如果是,则直接返回它的值。如果没有计算过,则按照背包问题的递推公式计算它的最优解,并将结果存入 `memo[i][j]` 中。
最后,我们调用 `dp(n, capacity)` 来计算问题的最优解。因为 `dp` 函数的参数是从 1 开始的,所以在计算时需要将 `items` 和 `values` 中的下标减 1。
示例使用:
```python
items = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
result = knapsack_memo(items, values, capacity)
print(result) # 输出 11
```
参考文献:
- [背包问题(Python实现)](https://blog.csdn.net/qq_36186690/article/details/81227809)