Поиск чисел в массиве определенным способом

19.07.2012, 19:13. **Показов** 753. **Ответов** 2

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

Здравствуйте
Имеем массив чисел A разной величины (возьмем 50-200), и имеем число N (например 700). Из массива A находим элементы, сумма которых будет максимально близка к N (но не больше N). Используем все элементы массива, 1 элемент можно использовать только 1 раз.

Или можно объяснить на линях. Имеем короткие линии разной длины. Из этих коротких линий нужно составить длинные, чтобы их длина максимально подбиралась к значению N (но не больше N).

Например:
A = 60, 130, 90, 50, 200, 110, 80, 220, 150, 70, 80, 100
N = 400

Получаем:
1: 70 + 130 + 110 + 90 = 400
2: 50 + 200 + 150 = 400
3: 100 + 80 + 220 = 400
4: 60 + 80 = 140

Как такое сделать ума не приложу.

@canopen · 19.07.2012, 20:38

Это задача о рюкзаке что ли?
http://ru.wikibooks.org/wiki/%... 1%86%D0%B5

19.07.2012, 20:44

Мне кажется больше похоже на "Задача об упаковке в контейнеры" - http://ru.wikipedia.org/wiki/%... 1%80%D1%8B

Сейчас ищу по этому

br-tree
		1
	Поиск чисел в массиве определенным способом 19.07.2012, 19:13. Показов 753. Ответов 2 Метки нет (Все метки) Здравствуйте Имеем массив чисел A разной величины (возьмем 50-200), и имеем число N (например 700). Из массива A находим элементы, сумма которых будет максимально близка к N (но не больше N). Используем все элементы массива, 1 элемент можно использовать только 1 раз. Или можно объяснить на линях. Имеем короткие линии разной длины. Из этих коротких линий нужно составить длинные, чтобы их длина максимально подбиралась к значению N (но не больше N). Например: A = 60, 130, 90, 50, 200, 110, 80, 220, 150, 70, 80, 100 N = 400 Получаем: 1: 70 + 130 + 110 + 90 = 400 2: 50 + 200 + 150 = 400 3: 100 + 80 + 220 = 400 4: 60 + 80 = 140 Как такое сделать ума не приложу.

@canopen 430 / 431 / 93 Регистрация: 16.07.2012 Сообщений: 886
	19.07.2012, 20:38	2
	Это задача о рюкзаке что ли? http://ru.wikibooks.org/wiki/%... 1%86%D0%B5 0

br-tree
	19.07.2012, 20:44	3
	Мне кажется больше похоже на "Задача об упаковке в контейнеры" - http://ru.wikipedia.org/wiki/%... 1%80%D1%8B Сейчас ищу по этому