下面是 gfg 中子集求和问题的代码。请告诉我它有什么问题
Below is the code for subset sum problem in gfg. Please tell me what is wrong in it
#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
实际答案应该是 YES,但显示为 NO。
#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;
}
这是更正后的代码。
#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 实际答案应该是 YES,但显示为 NO。
#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;
}
这是更正后的代码。