首页蛮力法0/1背包问题代码

蛮力法0/1背包问题代码

时间: 2024-08-13 18:05:23 浏览: 98

蛮力法（Brute Force）也称为暴力枚举法，通常用于解决最优化问题，如背包问题中0/1背包问题，它涉及到在给定容量和物品价值的情况下，选择哪些物品装入背包以最大化总价值。这里是一个简单的Python代码示例，使用动态规划来求解0/1背包问题： ```python def knapsack(items, capacity): n = len(items) # 物品数量 dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 初始化动态规划表 # 动态规划过程 for i in range(1, n + 1): # 遍历每个物品 weight, value = items[i - 1] # 当前物品重量和价值 for w in range(1, capacity + 1): # 遍历所有可能的背包容量 if weight <= w: # 如果当前物品能完全装入背包 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value) # 选择装或不装 else: # 如果当前物品装不下 dp[i][w] = dp[i - 1][w] # 不装，保持之前的最大价值 # 返回最大价值 return dp[n][capacity] # 示例物品和背包容量 items = [(2, 3), (3, 4), (4, 5)] capacity = 5 print(knapsack(items, capacity))

阅读全文