打家劫舍问题python代码
时间: 2024-09-27 22:02:02 浏览: 15
打家劫舍问题,也叫0-1 Knapsack Problem),是一个经典的动态规划问题。在Python中,可以使用二维数组来存储状态并递推求解。以下是简化版的Python代码:
```python
def knapSack(W, wt, val, n):
K = [[0 for w in range(W+1)] for i in range(n+1)]
# 构建表,K[i][w]表示前i个物品,总重量不超过w的情况下能获取的最大价值
for i in range(1, n+1):
for w in range(1, W+1):
if wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
# 示例数据
val = [60, 100, 120] # 物品的价值
wt = [10, 20, 30] # 物品的重量
W = 50 # 背包容量
n = len(val) # 物品总数
max_value = knapSack(W, wt, val, n)
print("最大价值:", max_value)
相关问题
打家劫舍二叉树Python
以下是一个用Python解决打家劫舍二叉树问题的示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root):
def helper(node):
if not node:
return (0, 0)
left = helper(node.left)
right = helper(node.right)
# 偷当前节点的金额
rob_value = node.val + left[1] + right[1]
# 不偷当前节点的金额
not_rob_value = max(left) + max(right)
return (rob_value, not_rob_value)
return max(helper(root))
# 创建一个二叉树
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)
# 调用函数计算最大金额
result = rob(root)
print("最大金额为:", result) # 输出:7
```
打家劫舍2python
打家劫舍2是一道动态规划问题,可以使用类似于打家劫舍1的思路解决。不同的是,在这道题目中,房屋排列成了一个环形,也就是说第一个房屋和最后一个房屋是相邻的。因此,我们需要分别计算偷第一个房屋和不偷第一个房屋两种情况下的最大收益,最后取两种情况中的较大值即可。
以下是Python的代码实现:
```python
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
return max(self.robRange(nums, 0, len(nums) - 2), self.robRange(nums, 1, len(nums) - 1))
def robRange(self, nums: List[int], start: int, end: int) -> int:
n = len(nums)
dp_i_1, dp_i_2 = 0, 0
dp_i = 0
for i in range(end, start - 1, -1):
dp_i = max(dp_i_1, nums[i] + dp_i_2)
dp_i_2 = dp_i_1
dp_i_1 = dp_i
return dp_i
```
在这个解法中,`robRange` 函数用于计算不同范围内的最大收益。我们使用 `dp_i_1` 和 `dp_i_2` 分别表示前两个子问题的最大收益,`dp_i` 表示当前子问题的最大收益。在每次迭代中,我们根据状态转移方程 `dp[i] = max(dp[i-1], nums[i] + dp[i-2])` 来更新 `dp_i`、`dp_i_1` 和 `dp_i_2` 的值。最后返回 `dp_i` 即可得到该范围内的最大收益。
在 `rob` 函数中,我们分别计算偷第一个房屋和不偷第一个房屋两种情况下的最大收益,并取两种情况中的较大值返回。其中 `robRange(nums, 0, len(nums) - 2)` 表示偷第一个房屋的情况,`robRange(nums, 1, len(nums) - 1)` 表示不偷第一个房屋的情况。