|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dima Shpilevsky 2:450/240.13 12 Mar 2002 16:57:54
To : Dmitry Zhadanoff
Subject : все возможные суммы элементов массива
--------------------------------------------------------------------------------
Еха-ноха, Dmitry! Съешь ещё этих мягких французских булок, да выпей чаю!
Помню когда-то , 11 Mar 02 в 19:27, Dmitry Zhadanoff напиcал для Andrew
Doroshev нижecлeдyющee:
>>> Есть массив из 100 элементов. Как составить список, включающий все
>>> возможные суммы элементов этого массива?
AD>> Количество комбинаций будет 2^100=1267650600228229401496703205376
AD>> Дмитрий, Вы ничего не забыли нам сообщить?
DZ> Прошу прощения, просто тороплюсь очень, срочно все:(
DZ> Hа самом деле задача следующая: есть около 100 чисел, из которых нужно
DZ> выбрать несколько, дающих в сумме максимально приближенное к S
DZ> значение. То есть: набрать варианты счетов для баланса с минимальным
DZ> отклонением от этого баланса. Количество составляющих сумму -
DZ> фиолетово,
если фиолетово, то нечего и заморачиваться :)
сортируешь массив по возрастанию и последовательно суммируешь элементы до
превышения суммой значения S. По факту превышения смотришь, что ближе к S -
превышающая или недостающая сумма.
DZ> но если можно минимизировать - хорошо. Вспомнил задачу о
DZ> монетах - но там целочисленно все было, а здесь - реальные числа. Что
DZ> можете посоветовать до утра (и на Delphi/Pascal в netmail 2:5095/1.40
DZ> если есть решения, плз)?
а если не филоетово, то тут нужны спец. методы. Симплексы всякие. Hавскидку
не посоветую :(
...и когда я умру, мои уши, как папоротники, прорастут из земли.
WBR, Чёрный Миссионер [Sacred Shrub Clan]
[Орден Могильной Лопаты]
---
* Origin: dmg.da.ru * trueblacker@avest.org * ICQ 24774275 (2:450/240.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
все возможные суммы элементов массива 