c++01背包问题

01背包问题是动态规划中的经典问题，用于在有限容量下选择物品以最大化价值。以下是其核心要点总结：

C++实现思路：

使用二维数组 `dp[i][j]` 表示前i个物品在容量j下的最大价值。状态转移方程为：

`dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])`

优化空间后，可使用一维数组 `dp[j]`，从后往前更新。

关键点：

- 物品不可重复选取

- 状态转移需考虑是否装入当前物品

- 时间复杂度为 O(nC)，空间为 O(C)

01背包是解决资源分配问题的基础模型，广泛应用于实际场景。