Определить, можно ли из элементов массива составить сумму, равную заданному числу

@Irene_Novikova_ · Регистрация: 22.03.2018

Author24 — интернет-сервис помощи студентам

Помогите, пожалуйста, с алгоритмом. Задан массив из N чисел и какое-нибудь число q. Требуется определить, можно ли из элементов массива составить сумму, равную числу q? Например: arr={1,4,8,2,16}, q=21 1+4+16=21, Ответ: да;

@Shamil1 · 23.03.2018, 12:22

Python

def solve(a, m):
    s = {0}
    for n in a:
        if n <= m:
            b = [x + n for x in s if x + n <= m]
            s.update(b)
    return m in s

@~~ili1~~ · 24.03.2018, 08:35

Irene_Novikova_
Можно написать N - кратный цикл типа
FOR i1 = 0 TO 1
FOR i2 = 0 TO 1
...
FOR in = 0 TO 1

S = i1 * x(1) + i2 * x(2) + ... + in * x(n)
IF S = Q THEN PRINT "YES"
GOTO 777

NEXT
...
NEXT

PRINT "NO"
777:
где x() - массив заданных чисел, Q - наперед заданное число
Как только (в цикле) будет найдена нужная сумма, так печатается ответ YES
и программа выходит далее на метку 777.
В противном случае, по окончании работы цикла выдается ответ NO.

@Irene_Novikova_ 0 / 0 / 0 Регистрация: 22.03.2018 Сообщений: 1
		1
	Определить, можно ли из элементов массива составить сумму, равную заданному числу 22.03.2018, 22:05. Показов 1916. Ответов 2 Метки нет (Все метки) Помогите, пожалуйста, с алгоритмом. Задан массив из N чисел и какое-нибудь число q. Требуется определить, можно ли из элементов массива составить сумму, равную числу q? Например: arr={1,4,8,2,16}, q=21 1+4+16=21, Ответ: да; 0

@~~ili1~~ Заблокирован
	24.03.2018, 08:35	3
	Irene_Novikova_ Можно написать N - кратный цикл типа FOR i1 = 0 TO 1 FOR i2 = 0 TO 1 ... FOR in = 0 TO 1 S = i1 * x(1) + i2 * x(2) + ... + in * x(n) IF S = Q THEN PRINT "YES" GOTO 777 NEXT ... NEXT PRINT "NO" 777: где x() - массив заданных чисел, Q - наперед заданное число Как только (в цикле) будет найдена нужная сумма, так печатается ответ YES и программа выходит далее на метку 777. В противном случае, по окончании работы цикла выдается ответ NO. 0