背包问题是一类经典的组合优化问题，主要分为 **0/1 背包** 和 **分数背包** 两种类型。在 0/1 背包中，每个物品只能选择一次或不选，而分数背包允许选择物品的一部分。以下将分别介绍这两种问题的 Python 实现方式，并提供详细的代码和解释。 ### 0/1 背包问题的动态规划实现 动态规划是解决 0/1 背包问题的常用方法。通过构建一个二维数组来记录在特定物品数和容量下的最大价值。 ```python def knapsack(wt, val, n, W): # 初始化一个二维数组 K，K[i][w] 表示前 i 个物品在容量为 w 时的最大价值 K = [[0 for x in range(W + 1)] for x in range(n + 1)] for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: K[i][w] = 0 elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-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) print(knapsack(wt, val, n, W)) ``` 该实现基于构建一个二维数组，其中 `K[i][w]` 表示在前 `i` 个物品中选择，且总容量不超过 `w` 时所能获得的最大价值[^1]。 ### 使用 NumPy 实现 0/1 背包问题 可以利用 `numpy` 库简化数组操作，提高效率。 ```python import numpy as np def zero_one_knapsack(): n = int(input("请输入物件总数：")) v_str = input("请输入每件物品的价值：(逗号隔开) ") v_list = list(map(int, v_str.split(","))) v = [0] + v_list w_str = input("请输入每件物品的质量：(逗号隔开) ") w_list = list(map(int, w_str.split(","))) w = [0] + w_list C = int(input("请输入背包大小：")) m = np.zeros([n + 1, C + 1], dtype=np.int) for i in range(1, n + 1): for W in range(1, C + 1): if w[i] > W: m[i, W] = m[i-1, W] else: m[i, W] = max(m[i-1, W], v[i] + m[i-1, W - w[i]]) print(m) return m[n, C] if __name__ == "__main__": zero_one_knapsack() ``` 该方法通过 `numpy` 构建一个 `(n+1) × (W+1)` 的二维数组，逐行更新数组值，最终得到最优解[^2]。 ### 分数背包问题的贪心算法实现 分数背包问题可以通过贪心算法解决，优先选择单位重量价值最高的物品。 ```python def fractional_knapsack(goods, W): # 按照单位价值从高到低排序 goods.sort(key=lambda x: x[0]/x[1], reverse=True) total_value = 0 m = [0 for _ in range(len(goods))] # 记录每个物品被选中的比例 for i, (value, weight) in enumerate(goods): if W >= weight: m[i] = 1 total_value += value W -= weight else: m[i] = W / weight total_value += m[i] * value W = 0 break return total_value, m # 示例数据 goods = [(60, 10), (100, 20), (120, 30)] W = 50 total_value, fractions = fractional_knapsack(goods, W) print("最大价值为:", total_value) print("物品选择比例:", fractions) ``` 该实现基于物品的单位重量价值进行排序，然后依次选取物品，直到背包装满[^4]。 ### 总结 - **0/1 背包**：使用动态规划方法，构建二维数组存储子问题的最优解。 - **分数背包**：采用贪心策略，优先选择单位价值最高的物品。 以上代码均适用于不同规模的背包问题，可根据具体需求调整输入方式和数据结构。 ---