空间优化版0-1背包如何获取被选中的物品元素

错误根源 #

你当前在DP更新内层循环里直接标记used[i] = 1的逻辑不成立：只要物品i对任意容量j的DP值产生了更新就会被标记为选中，但后续其他物品的更新可能会覆盖该决策，导致最终最优解中实际并未选中i，这就是你统计的总收益、总重量远超预期的核心原因。
一维DP数组的计算逻辑本身是正确的，你只需要去掉内层循环里的used[i]赋值，在DP数组计算完成后单独回溯选中的物品即可，常用有两种实现方案：

方案1：仅用最终一维DP数组倒推（空间开销最低） #

该方案不需要额外存储历史DP状态，仅依靠最终的DP数组、重量、价值数组倒序遍历物品判断是否选中，空间开销保持接近O(capacity)的优化水平。

实现逻辑 #

1. 正常计算得到最终的一维DP数组
2. 初始化剩余容量为背包最大容量remain = capacity，used数组全置为0
3. 从最后一个物品倒序遍历到第一个物品：
   • 若剩余容量大于等于当前物品重量，且DP[remain] == DP[remain - weight[i]] + profit[i]，说明该物品在最优解中被选中
   • 标记该物品为已选，剩余容量减去当前物品重量
   • 剩余容量为0时可提前退出遍历

代码示例 #

// 计算DP数组（删除原有循环内的used[i]赋值逻辑）
int *DP = (int*)calloc(capacity + 1, sizeof(int));
for (int i = 0; i < n; i++) {
    // 内层循环下限优化为weight[i]，避免无效判断
    for (int j = capacity; j >= weight[i]; j--) {
        if (DP[j] < DP[j - weight[i]] + profit[i]) {
            DP[j] = DP[j - weight[i]] + profit[i];
        }
    }
}

// 回溯标记选中物品
int *used = (int*)calloc(n, sizeof(int));
int remain = capacity;
for (int i = n - 1; i >= 0; i--) {
    if (remain >= weight[i] && DP[remain] == DP[remain - weight[i]] + profit[i]) {
        used[i] = 1;
        remain -= weight[i];
    }
    if (remain == 0) break;
}

用你提供的示例验证，回溯得到的选中物品总收益为47，总重量不超过8，符合预期。该方案默认返回其中一个最优解，若需要枚举所有最优解需额外加递归回溯逻辑。

方案2：保存DP历史状态回溯（逻辑简单不易错） #

如果对空间开销容忍度更高，可以额外存储每一步处理完物品后的DP状态，回溯逻辑更直观，不容易出现顺序错误。

实现逻辑 #

1. 定义二维数组dp_history[n][capacity+1]，每处理完第i个物品，就把当前一维DP数组拷贝到dp_history[i]
2. 倒序遍历物品，对比第i个物品处理前后的同容量DP值：如果dp_history[i][j] > dp_history[i-1][j]，说明该物品被选中，减去对应重量继续回溯即可。

内容的提问来源于stack exchange，提问作者Black