c++ 布尔背包dp

在 C++ 中，布尔背包（0-1 Knapsack Problem）是一种动态规划问题，用于解决物品分配问题，其中每个物品都有一个价值和重量，目标是在不超过背包容量的前提下选择物品，使得总价值最大。通常涉及二维数组（或称为状态表），其中 `dp[i][j]` 表示在前 i 件物品中选取总重量不超过 j 的物品的最大价值。

动态规划求解过程通常分为以下几个步骤：

1. 初始化：`dp[j] = 0` （当物品数为0或背包容量为0时，价值为0）；
2. 状态转移方程：对于第 i 件物品和背包容量 j，
- 如果物品 i 的重量大于当前背包容量 j，则不选这件物品，`dp[i][j] = dp[i-1][j]`；
- 否则，可以选择这件物品，`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`，即取或不取第 i 件物品，并选择价值更大的结果；
3. 结果：最终的解在 `dp[n][W]` 中，其中 n 是物品总数，W 是背包容量。