|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Zhadanoff 2:5095/1.40 12 Mar 2002 22:55:26
To : Dima Shpilevsky
Subject : все возможные суммы элементов массива
--------------------------------------------------------------------------------
Tuesday March 12 2002 15:57, Dima Shpilevsky wrote to Dmitry Zhadanoff:
DZ>> к S значение. То есть: набрать варианты счетов для баланса с
DZ>> минимальным отклонением от этого баланса. Количество составляющих
DZ>> сумму - фиолетово,
DS> если фиолетово, то нечего и заморачиваться :)
Меня волнует немного другая вещь. Есть еще массив некоторых
весов/характеристик элементов. Так что - если решений несколько(много), надо
найти те, у которых помимо всего прочего суммарный "вес" был
минимальным/максимальным. Вот.
DS> сортируешь массив по возрастанию и последовательно суммируешь
DS> элементы до превышения суммой значения S. По факту превышения
DS> смотришь, что ближе к S - превышающая или недостающая сумма.
И получу ерунду всякую. Ты гарантируешь, что это будет самое точное число?
1,1,1,1,1,5,5,5. А надо набрать 6 или 7. Я правильно понял?
DS> а если не филоетово, то тут нужны спец. методы. Симплексы всякие.
DS> Hавскидку не посоветую :(
Вобщем у меня такие числа, что если их округлить - то рюкзак почти всегда
собирается точно. Возможную ошибку округления уменьшаю, задавая немного другую
конечную сумму. Пока этого достаточно(быстро, правда делается массив около 260
мегов в памяти:)), горячка прошла, но хотелось бы узнать алгоритм задачи о
рюкзаке, но для действительных чисел (2 знака после запятой) и заданного
возможного отклонения. Где поискать?
. Bye !
---
* Origin: e-mail: hostage(at)mail.ru (2:5095/1.40)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
