задачка... на алгоритмизацию

[Cyrax]

доброго всем времени суток!

уважаемые, подскажите алгоритм решения такой задачи:
имеется ряд числовых значений и какая-то определенная сумма.
например:
ряд чисел

5.02

46

10

102.14

70

38

сумма:
182.14
требуется: из приведенного ряда чисел подобрать такие, что бы в результате получилас указанная сумма (или, хотя бы, сумма наиболее приближенная к указанной).

у кого какие мысли по этому поводу?

[Mikle]

Число вариантов сочетаний:

из шести по ноль - 1 (это тоже вариант, если сумма=0)
из шести по одному - 6
из шести по два - 15
...
из шести по пять -6
из шести по шесть - 1

бином Ньютона. По-моему перебрать все варианты и выбрать ближайший не проблема.

[vrodo]

Думаю что можно проще
D = 0 ' delta
X = 0 ' наше число
Y = 234 ' Ваша сумма
A(1 to 6)=3,4,50,54,100,30
выстраиваем их попорядку
A(1 to 6)=100,54,50,30,4,3
i = 1
Metka:
Берем самое большое если оно не больше A(i) <= (Y - X) И i <= 6
x = x + A(i)
Иначе
i=i+1
Goto Metka:

Чесно печатал совершенно Случайные Числа
Начиная от Y и заканчивая массивом А

[_NeoN_]

если не знаешь как делать то делай перебором.. запоминай все суммы и потом самую приближенную выбирай...

[Cyrax]

чего-то меня клинит... по черному... будь она не ладна эта задачка
пока получается, так сказать, промежуточный результат...
прохожусь в цикле по всему списку от самого большого вниз и считаю сумму...
после этого надо бы пройтись еще раз, уже по двум спискам (исходному и полученному после первого цикла), что бы подогнать результат еще точнее... но вот как это реализовать? чего-то никак не придумывается...
народ глянте проект, может чего подскажете...

[SeRRg]

P.S. Все сказанное ниже является моим предположением, и я могу ошибаться.
Тут дело совсем просто. Ты только все усложняешь:
Твоя прога находит НАИБОЛЬШЕЕ число из СУММЫ, меньшей искомой.
А надо находить еще и НАИМЕНЬШЕЕ из БОЛЬШИХ.
Тогда у тебя будет наиболее близкое.
Я вот тут дописал кое-чего. У меня работает.
Посмотри и проверь.

P.S. Я могу ошибаться.

[vrodo]

Я нашел в своем предложении ошибку
попробуйте этот алгоритм для порядка если число которое надо найти = 64
60
30
34
3
получится 63
хотя можно получить и 64

так что надо наверно
надо попробовать сделать еще циклы в котором будет учитыватся весь массив без последного верхнего числа и только в том случае если сумма оставшихся чисел >= 64

и тестировать на соответствие
если old_summ < new_summ <=trebuemaja_summa то old_summ =new_summ

[SeRRg]

Вообще-то ты прав...
Но тогда, следуя логике нужно:
1.Применить описанную процедуру к массиву.
2.Запомнить лучшее.
3.Уменьшить массив на одно число. (ведь и среди других может быть такое же)
4.Если чисел больше двух, то перейти к (1).
5.Выбрать из получившегося оптимальный вариант.
Я думаю Так.
Поправьте меня, если не так.

[vrodo]

угу
тоесть найти найти значение где abs(trebuemaja_summ-new_summ) будет наименьшим

[Mikle]

Не пойму, в чем проблемы. Пусть дано N чисел, тогда число вариантов - 2^N. Номеру K соответствует сумма тех элементов массива, соответствующий бит которого в K установлен. Пробегаем от 0 до (2^N)-1, находим сумму и сравниваем с необходимой. Вот код формы, рабочий. По клику мышкой - рассчет:

Option Explicit
Const Size = 6
Dim m(Size - 1) As Single, Summ As Single

Private Sub Form_Click()
Dim n As Long
Dim Num As Long
Dim tmpRes As Single
Dim tmpSumm As Single

Me.Cls
Randomize Timer
'Заполняем массив
For n = 0 To Size - 1
m(n) = (Rnd - 0.5) * 100
Next n
Summ = (Rnd - 0.5) * 100

tmpSumm = 0
Num = 0
tmpRes = Abs(Summ - tmpSumm)
For n = 0 To (2 ^ Size) - 1
tmpSumm = TestSumm(n)
If Abs(Summ - tmpSumm) < tmpRes Then
tmpRes = Abs(Summ - tmpSumm)
Num = n
End If
Next n

For n = 0 To Size - 1
Me.Print n, m(n)
Next n
Me.Print "Дана сумма:"; Summ
Me.Print

tmpSumm = 0
For n = 0 To Size - 1
If ((2 ^ n) And Num) Then Me.Print n, m(n)
Next n
Me.Print "Итог сумма:", TestSumm(Num)

End Sub

Private Function TestSumm(NN As Long) As Single
Dim n As Long
TestSumm = 0
For n = 0 To Size - 1
If ((2 ^ n) And NN) Then TestSumm = TestSumm + m(n)
Next n
End Function

[Cyrax]

2 Mikle:
башое пасибо... но, объясни, пжалста, что это такое? в смысле, как называется этот алгоритм...
и где можно посмотреть подобные задачки (с возможными их решенями).
я думаю это не только мне будет полезно, но и многим посетителям форума...

[corgi]

я бы сказал так это алгоритм "первое что пришло в голову"
2Mikle это не наезд а просто выразился я так, может чуток грубо, но все же
2Cyrax
если хочешь глянь тута, больше ничего особого в сети не знаю

[Mikle]

Согласен - первое, что пришло.
Где есть еще решения таких задач?.. не знаю, я их сам решаю.
А алгоритм можно оптимизировать, например заменить степень сложением (равным количеством!!!), но я не сделал этого, чтобы не потерять понятность.

[Cyrax]

2 corgi:
спасибо... ну я полез сливать...
а то все WinAPI, да WinAPI... а такие элементарные (почти) вещи ставят в тубик... надо бы это исправить

[v-adix]

мне кажется, что если чисел немного, то надо просто сделать перебор. цикл примерно такой:

for i = 1 to сколькочисел
for k = 1 to сколькочисел

запомнить все суммы в массив а потом посмотреть самый близкий ответ

[Mikle]

v-adix
Так ты получишь только суммы из ДВУХ чисел, причем среди них недопустимые - когда i=k. Да и зачем массив, если результаты можно сравнивать СРАЗУ.