Помогите с алгоритмом...

← →
Cranium (2003-04-01 17:26) [0]

Есть некий набор цисел к примеру (4500, 8352, 4235, 5500, 123, 728, 63, 744), надо выбрать из этого набора цифры так, чтобы в сумме было заданное число например 10000, если это не возможно, то число близкое к 10000, но с заданным процентом отклонения, например 5%, тоесть удовлетворительный результат лежит в диапазоне 9500 - 10500....
У кого какие соображения?

← →
MBo (2003-04-01 17:33) [1]

Увы, перебором.
Задача о рюкзаке.

← →
ZrenBy (2003-04-01 17:34) [2]

При большом наборе - Метод Монте-Карло самое то.

← →
eLVik (2003-04-01 17:40) [3]

В принципе существует несколько выборок из данного набора, удовлетворяющих условию.

Уточни! Нужно рассматривать все выборки или определённые?

← →
Cranium (2003-04-01 17:44) [4]

Достаточно одной выборки удовлетворяющий условию......

← →
Cranium (2003-04-01 18:02) [5]

> ZrenBy © (01.04.03 17:34)
> При большом наборе - Метод Монте-Карло самое то.

Уточни или ссылку где почитать...

← →
ZrenBy (2003-04-01 18:08) [6]

Есть исходник на С (67 строчек), если хочешь - скину.

← →
kravchuk (2003-04-01 18:14) [7]

По- моему можно использовать динамическое программирование,
http://dyatl.narod.ru/olympic/alg/dyn.htm пример 3, только его надо малехо переделать

← →
Думкин (2003-04-02 05:41) [8]

В постановке задачи речь идет о цифирях, а не о числах.
посему требую продолжения банкета и точной постановки.

← →
Cranium (2003-04-02 13:04) [9]

Конечно же числа...

← →
Думкин (2003-04-03 05:34) [10]

> Cranium © (02.04.03 13:04)
> Конечно же числа...

Тогда, как и говорилось, - задача о рюкзаке. ЛП.
Задача проста. Но за 100 ьаков станет еще проще %-)

Помогите с алгоритмом... Найти похожие ветки