c++ - 以下是 gfg 中子集和问题的代码。请告诉我它有什么问题
问题描述
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(int a[], int n, int s)
{
bool dp[n+1][s+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<s+1;j++)
{
if(i==0)
dp[i][j] = false;
if(j==0)
dp[i][j] = true;
if(a[i-1]<=j)
dp[i][j] = dp[i-1][j-a[i-1]] || dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][s];
}
int main()
{
//code
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
int s=0;
for(int i=0;i<n;i++){
cin>>arr[i];
s+=arr[i];
}
if(s%2==0)
{
s/=2;
if(check(arr,n,s))
cout<<"YES\n";
else
cout<<"NO\n";
}
else
cout<<"NO\n";
}
return 0;
}
问题是给定一组数字,检查它是否可以分成两个子集,使得两个子集中的元素之和相同。
对于测试用例;4 1 5 11 5 输出将为 YES,因为存在 {1, 5, 5} 和 {11} 两个子集。
上述测试用例通过但显示错误答案 8 479 758 315 472 730 101 460 619 实际答案应为“是”,但显示为“否”。
解决方案
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(int a[], int n, int s)
{
bool dp[n+1][s+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<s+1;j++)
{
if(i==0)
dp[i][j] = false;
else if(j==0)
dp[i][j] = true;
else if(a[i-1]<=j)
dp[i][j] = dp[i-1][j-a[i-1]] || dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][s];
}
int main()
{
//code
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
int s=0;
for(int i=0;i<n;i++){
cin>>arr[i];
s+=arr[i];
}
if(s%2==0)
{
s/=2;
if(check(arr,n,s))
cout<<"YES\n";
else
cout<<"NO\n";
}
else
cout<<"NO\n";
}
return 0;
}
这是更正后的代码。
推荐阅读
- javascript - 在 json 数组中的每个 json 对象中添加另一个 json 对象
- django - django 是否可以一次聚合查询集的所有字段
- php - Unity C# - 运行 php 并读取 html 结果
- python - 检测熊猫列中两个刺之间的差异并将它们复制到另一列中
- c# - 调整图像大小并另存为文件
- javascript - 使用 setInterval 刷新 div 但它扰乱了视图页面的模板
- c++ - 使用opencv cap无法使用While循环调用函数两次
- backup - 赛门铁克网络备份 8.1
- java - SpringBoot 中的 NoSuchElementException @ExceptionHandler 不起作用
- docker - nginx 容器:未知指令“事件”,.conf 错误