# 背包问题

> 背包问题（英语：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。

- ID: m04311
- 分类: business
- 领域: 管理学

## 定义

给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品组合，使得总价值最高？这是一个经典的NP-完全问题。脚手架作用： 隐喻资源受限下的价值最大化。无论是时间管理（一天24小时）、投资组合还是人生选择，本质上都是背包问题。它告诉我们，贪心策略（只拿单位价值最高的）往往不是全局最优，完美的解法可能极其昂贵，我们需要近似解。

## 机制

在容量约束下选物品使总价值最大，是组合优化中的NP-完全问题；最优需枚举（或动态规划）全部可行组合，规模大时计算爆炸，故常取近似/启发式解。

## 练习

明确"容量"（时间、预算、权重）与每件"价值/成本"；用动态规划求精确解（小范围）或贪心/近似算法求可行解；按单位价值排序并权衡约束，接受次优。

## 脚手架用法

隐喻资源受限下的价值最大化。无论是时间管理（一天24小时）、投资组合还是人生选择，本质上都是背包问题。它告诉我们，贪心策略（只拿单位价值最高的）往往不是全局最优，完美的解法可能极其昂贵，我们需要近似解。

[阅读网页](https://thinkingmodels.site/entries/detail/m04311)