时间戳

首页 > 解决方案 > 为什么我的 3-Partitioning 问题无法通过给定的测试用例？（3-分区问题）

c++ - 为什么我的 3-Partitioning 问题无法通过给定的测试用例？（3-分区问题）

问题描述

参考以下内容： 3-PARTITION 问题

有人可以解释为什么在 R. Gurung 的 cpp 解决方案中，我们从 sum 开始我们的 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。

有人可以解释一下这个缺陷吗？我不明白，为什么它在错误时会通过法官？

编辑-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)。请解释我的解决方案中的错误。

标签： c++algorithmdynamic-programmingpartitioningarray-algorithms

解决方案

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

推荐阅读