Условие:
Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей, сумма элементов которой равна w, либо установите, что искомой подпоследовательности не существует.
Формат входного файла:
Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.
Формат выходного файла:
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите −1.
Ограничения:
1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000
Помогите исправить ошибку в восстановлении ответа.
Вот код:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <stdio.h>
using namespace std;
int n,w,i,j;
ofstream fo("output.txt");
ifstream fi("input.txt");
int main (){
fi >> n >> w;
int* A = (int*)malloc(sizeof(int)*(n+1));
int* B = (int*)malloc(sizeof(int)*(n+1));
int* S = (int*)malloc(sizeof(int)*(w+1));
for (i = 1; i <= n; i ++)
fi >> A[i];
S[0] = 1;
for (j = 1; j <= w; j ++)
S[j] = 0;
for (i = 1; i <= n; i ++){
for (j = w; j >= A[i]; --j){
S[j] |= S[j - A[i]];
}
}
j = w;
if(S[w]){
for (i = n; i >= 1; i --){
if (j > A[i]){
B[i] = 1;
j -= A[i];
} else {
B[i] = 0;
}
}
for(i = 1; i <= n; i++)
fo << B[i] << " ";
} else {
fo << -1;
}
}
