子集和问题Java实现异常：目标容量匹配错误排查

你猜的没错，问题确实出在数组索引从0开始的处理错误上，核心是你没有正确对应容量值和数组索引的关系，导致程序实际上在检查“是否能装满容量3”而不是你需要的4。下面一步步拆解错误点和修复方案：

1. 数组维度定义错误 #

你定义的二维数组：

boolean B[][] = new boolean[p.size()][C];
boolean U[][] = new boolean[p.size()][C];

第二维长度是C，意味着索引范围是0到C-1，只能表示容量0到C-1的状态，但我们需要检查的是“恰好装满容量C”，所以必须把数组长度改为C+1，这样索引C就对应容量C：

boolean B[][] = new boolean[p.size()][C+1];
boolean U[][] = new boolean[p.size()][C+1];

2. 第一行初始化的逻辑错误 #

你先初始化了B[0][0] = true;（表示容量0可以用0个容器装满），但随后的循环从j=0开始遍历，会把B[0][0]重新设为false（因为j=0不等于第一个容器的容量1），这直接破坏了基础状态。应该调整循环从j=1开始，保留j=0的初始值：

// prima riga - caso base
for(j = 1; j <= C; j++) {  // 这里j到C，对应容量1到C
    if(j == p.get(0).getCapienza()) {
        B[0][j] = true;
        U[0][j] = true;
    } else {
        B[0][j] = false;
        U[0][j] = false;
    }
}

3. 通用情况的循环范围错误 #

原来的循环j < C只遍历到容量C-1，需要改成j <= C才能覆盖到容量C的情况：

for(i = 1; i < p.size(); i++) {
    for(j = 0; j <= C; j++) {  // j到C，对应容量0到C
        if(j >= p.get(i).getCapienza()) {
            B[i][j] = B[i-1][j] || B[i-1][j - p.get(i).getCapienza()];
            U[i][j] = B[i-1][j-p.get(i).getCapienza()];
        } else {
            B[i][j] = B[i-1][j];
            U[i][j] = false;
        }
    }
}

4. 结果检查与回溯的起始值错误 #

原来的代码检查B[p.size()-1][C-1]，这是在检查“是否能装满容量C-1”（比如C=4时是3），完全不符合需求。同时回溯的起始j值是C-1，也是错的，应该改成：

if(!B[p.size()-1][C]) {  // 检查容量C的状态
    System.out.println("-1");
}else {
    i = p.size()-1;
    j = C;  // 从容量C开始回溯
    while( i >= 0 && j >= 0) {
        if(U[i][j]) {
            num_cont++;
            System.out.println("Usato: "+p.get(i).getId() +" capienza:" + p.get(i).getCapienza());
            j = j - p.get(i).getCapienza();
        }
        i--;
    }
}

修复后的测试结果 #

当你用C=4测试时，程序会正确找到组合：c3(3)+c1(1)，总和为4，返回的num_cont是2，符合预期。

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