Возможные суммы в массиве

@stanis-morozov · Регистрация: 18.03.2012

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

Добрый вечер!
Задача следующая: дан массив из N элементов (1 <= N <= 500). Каждый элемент p такой что 1 <= p <= 1000. И дано число k, (1 <= k <= 100000). Требуется узнать, возможно ли суммируя элементы массива, получить ровно число k. Каждый элемент можно использовать только один раз. При этом желателен максимально быстрый алгоритм. Возможно ли это узнавать за O(N)?
Заранее спасибо за помощь!

@Хохол · 07.12.2012, 17:14

Нельзя за O(N). Почитайте про задачу о рюкзаке.

@stanis-morozov 15 / 15 / 3 Регистрация: 18.03.2012 Сообщений: 91
		1
	Возможные суммы в массиве 05.12.2012, 23:23. Показов 817. Ответов 1 Метки нет (Все метки) Добрый вечер! Задача следующая: дан массив из N элементов (1 <= N <= 500). Каждый элемент p такой что 1 <= p <= 1000. И дано число k, (1 <= k <= 100000). Требуется узнать, возможно ли суммируя элементы массива, получить ровно число k. Каждый элемент можно использовать только один раз. При этом желателен максимально быстрый алгоритм. Возможно ли это узнавать за O(N)? Заранее спасибо за помощь! 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	07.12.2012, 17:14	2
	Нельзя за O(N). Почитайте про задачу о рюкзаке. 0