We are given as input a set of integers X,..., Xn such that |X| +...+|X| =...

Transcribed Image Text:

We are given as input a set of integers X₁,..., Xn such that |X₁| +...+|X₂| = K. Give a dynamic programming algorithm that outputs whether it is possible to find ±1 coefficients a1, an such that a₁ X₁ + + an Xn = 0. 1 For example, if (X1,..., X5) = (1, 2, 3, 4, 4) the answer is yes, since 1+2 3+4-4 = 0, however, if (X₁,..., X4)= (2,3,7,3), then the answer is no, since none of the 24 possible ±1 combinations adds up to 0. Give a dynamic programming algorithm that solves this problem in time that is polynomial asAct a function of T and n. Go We are given as input a set of integers X₁,..., Xn such that |X₁| +...+|X₂| = K. Give a dynamic programming algorithm that outputs whether it is possible to find ±1 coefficients a1, an such that a₁ X₁ + + an Xn = 0. 1 For example, if (X1,..., X5) = (1, 2, 3, 4, 4) the answer is yes, since 1+2 3+4-4 = 0, however, if (X₁,..., X4)= (2,3,7,3), then the answer is no, since none of the 24 possible ±1 combinations adds up to 0. Give a dynamic programming algorithm that solves this problem in time that is polynomial asAct a function of T and n. Go