Нет, ваш алгоритм неверен.Ваш алгоритм следует за жадным подходом.Я реализовал ваш подход, и он не прошел этот тестовый случай: (Вы можете попробовать здесь )
Жадный алгоритм:
#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;
#define MXN 55
int a[MXN];
int main() {
//code
int t,n,c;
cin>>t;
while(t--){
cin>>n;
rep(i,n) cin>>a[i];
sort(a, a+n);
reverse(a, a+n);
ll sum1 = 0, sum2 = 0;
rep(i,n){
cout<<a[i]<<endl;
if(sum1<=sum2)
sum1 += a[i];
else
sum2 += a[i];
}
cout<<abs(sum1-sum2)<<endl;
}
return 0;
}
Тестовый случай:
1
8
16 14 13 13 12 10 9 3
Wrong Ans: 6
16 13 10 9
14 13 12 3
Correct Ans: 0
16 13 13 3
14 12 10 9
Причиной сбоя жадного алгоритма является то, что он не учитывает случаи, когда брать больший элемент в текущем наборе больших сумм, а в последующем гораздо меньший в наборе больших сумм, можно получить гораздо лучшие результаты.Он всегда старается минимизировать текущую разницу, не изучая и не зная дополнительных возможностей, в то время как в правильном решении вы можете включить элемент в больший набор и включить гораздо меньший элемент позже, чтобы компенсировать эту разницу, так же, как в приведенном выше тестовом примере.
Правильное решение:
Чтобы понять решение, вам нужно разобраться со всеми приведенными ниже проблемами по порядку:
Мой код (та же логика, что и this):
#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;
#define MXN 55
int arr[MXN];
int dp[MXN][MXN*MXN];
int main() {
//code
int t,N,c;
cin>>t;
while(t--){
rep(i,MXN) fill(dp[i], dp[i]+MXN*MXN, 0);
cin>>N;
rep(i,N) cin>>arr[i];
int sum = accumulate(arr, arr+N, 0);
dp[0][0] = 1;
for(int i=1; i<=N; i++)
for(int j=sum; j>=0; j--)
dp[i][j] |= (dp[i-1][j] | (j>=arr[i-1] ? dp[i-1][j-arr[i-1]] : 0));
int res = sum;
for(int i=0; i<=sum/2; i++)
if(dp[N][i]) res = min(res, abs(i - (sum-i)));
cout<<res<<endl;
}
return 0;
}