首页动态规划法完成0/1背包问题（pycharm代码）

动态规划法完成0/1背包问题（pycharm代码）

时间: 2025-01-18 18:02:42 浏览: 38

动态规划是一种解决最优化问题的方法，常用于求解涉及重叠子问题和最优子结构的问题，比如0/1背包问题。在这个问题中，给定一组物品，每件物品有自己的重量和价值，目标是在不超过背包容量的情况下选择物品，使得总价值最大。下面是一个简单的Python（PyCharm环境下）代码示例，展示了如何使用动态规划来解决0/1背包问题： ```python def knapsack(weights, values, capacity): n = len(weights) # 初始化一个二维数组，dp[i][j]表示前i件物品放满j千克背包的最大价值 dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 构建状态转移方程 for i in range(1, n + 1): # 遍历物品 for j in range(1, capacity + 1): # 遍历背包容量 if weights[i - 1] <= j: # 如果当前物品能装进背包 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) # 取选和不选的较大值 else: dp[i][j] = dp[i - 1][j] return dp[n][capacity] # 示例数据 weights = [10, 20, 30] values = [60, 100, 120] capacity = 50 max_value = knapsack(weights, values, capacity) print(f"背包可以达到的最大价值是: {max_value}")

阅读全文