为什么我的3分区问题未能通过给定的测试用例？ （3-分区问题）

Question

参考以下内容：3-PARTITION problem

有人可以解释为什么在R. Gurung的cpp解决方案中我们从总和开始j和k的循环吗？如果我们从0开始循环怎么办？

我对给定的解决方案做了如下修改：

#include <vector>
#include <bits/stdc++.h>
using namespace std;


int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  //bool dp[sum+1][sum+1];
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j <=2*(sum/3); j++)
    {
      for (int k = 0; k <=2*(sum/3); k++)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

  for(int i=0;i<=sum;i++)
  {
    for(int j=0;j<=sum;j++)
    {
      cout<<dp[i][j]<<" ";
    }
    cout<<'\n';
  }

  return dp[sum / 3][sum / 3];
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> a;

  int n;
  cin>>n;

  for(int i=0;i<n;i++)
  {
    int input;
    cin>>input;
    a.push_back(input);
  }


  cout<<partition3(a);
}

我在partition3（）中的循环几乎适用于所有解决方案，它甚至通过了法官的测试用例，并且似乎是正确的，除非我给出了特定的测试用例：

10
20 9 13 27 25 7 2 9 17 15

对于给定的测试用例，答案应为0这应该会使程序输出0。既然如此，每个人都应该得到48，而如果有人得到27，那么无论他如何选择，他都不能得到48。

但是我以前的算法，即通过程序的算法，输出1。

有人可以解释这个缺陷吗？我没有得到它，还有为什么它在出错时会通过法官？

EDIT-1

  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >=0; --j)
    {
      for (int k = sum; k >=0; --k)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

以上循环将正确的答案（0）输出到给定的测试用例。请在我的解决方案中说明错误。

Answer 1

假设R. Gurung函数正确。在[[dp和A之间有一个依赖项，因此您不能按照您的建议从头到尾填充它。