θ(s)内存约束下动态规划求解划分问题的元素归属判定方法

首先，你的代码里有个关键的DP转移错误需要先修正：当前逻辑会覆盖dp[1,j]的值，忽略了“不选当前元素”的情况。正确的转移应该是dp[1,j] = dp[0,j] || (j >= tab[i-1] && dp[0,j - tab[i-1]])，否则你的可达状态计算会出错。

接下来回到你的核心问题：用θ(s)内存回溯得到ownership数组。我们可以通过添加一个额外的int[] selected数组（大小为sum+1，属于θ(s)内存）来记录每个可达和最后是被哪个元素选中的。这样，当我们找到最优的子集和target后，就能从target倒推回0，标记每个被选中的元素。

具体思路 #

1. 修正DP转移逻辑：确保正确计算每个元素处理后的可达状态（选或不选当前元素）。
2. 添加selected数组：在DP过程中，当某个和j是通过选中当前元素才变为可达时，记录该元素的索引到selected[j]。
3. 倒推构建ownership数组：找到最接近sum/2的可达和target，然后从target开始，通过selected数组回溯，标记每个被选中的元素。

修改后的完整C#代码 #

public int SetsMinimum(int[] tab, out bool[] ownership) {
    int n = tab.Length;
    int sum = 0;
    foreach (int v in tab) sum += v;
    ownership = new bool[n];
    bool[] prevDp = new bool[sum + 1]; // 处理前i个元素的可达状态
    bool[] currDp = new bool[sum + 1]; // 处理前i+1个元素的可达状态
    int[] selected = new int[sum + 1]; // 记录每个和最后由哪个元素选中，-1表示未被选中
    Array.Fill(selected, -1); // 初始化所有值为-1

    prevDp[0] = true; // 初始状态：0和是可达的

    for (int i = 0; i < n; i++) {
        int num = tab[i];
        // 复制前一个状态（不选当前元素的情况）
        Array.Copy(prevDp, currDp, sum + 1);

        // 处理选当前元素的情况
        for (int j = num; j <= sum; j++) {
            if (prevDp[j - num] && !currDp[j]) {
                currDp[j] = true;
                selected[j] = i; // 记录这个和是由第i个元素选中得到的
            }
        }

        // 更新prevDp为当前状态，准备处理下一个元素
        (prevDp, currDp) = (currDp, prevDp);
        Array.Fill(currDp, false); // 重置currDp为false，避免干扰下一次循环
    }

    // 找到最优的target：最接近sum/2的可达和
    int target = 0;
    for (int j = sum / 2; j >= 0; j--) {
        if (prevDp[j]) {
            target = j;
            break;
        }
    }

    // 回溯构建ownership数组
    int currentSum = target;
    while (currentSum > 0) {
        int idx = selected[currentSum];
        if (idx == -1) break; // 理论上不会走到这里，因为target是可达的
        ownership[idx] = true;
        currentSum -= tab[idx];
    }

    // 计算最小差值
    return Math.Abs(sum - 2 * target);
}

代码解释 #

• DP数组优化：用两个一维数组prevDp和currDp交替存储状态，严格保持θ(s)内存复杂度。
• selected数组：当我们通过选中第i个元素得到和j时，selected[j]记录i。我们只在currDp[j]原本为false时更新，这样保证记录的是能到达j的其中一个元素（最优解可能有多个，我们只需要输出其中一个即可）。
• 回溯过程：从最优target出发，不断找到最后一个选中的元素，标记它为true，然后将currentSum减去该元素的值，直到currentSum为0。

复杂度分析 #

• 时间复杂度：O(n*s)，DP过程中每个元素遍历sum次，回溯过程最多遍历n次。
• 内存复杂度：θ(s)，prevDp、currDp和selected数组的大小都是sum+1，加上ownership数组（大小n，通常小于s，整体仍为θ(s)）。

这样既满足了内存和时间的要求，又能正确生成ownership数组。

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