Два динамических массива и перебор комбинаций элем. в них

[Константин Н.]

Уважаемые форумчане! Есть 2 динамических массива. Как бы перебрать все возможные комбинации элементов первого, одновременно проверяя значения соотвествующих элементов второго на удовлетворение определенному условию?
Если брать уже, то: Есть два динамических массива, в первом N элементов и во втором N элементов. Хотелось бы перебрать все возможные комбинации элементов первого, такие, чтобы элементы второго, под теми же номерами, в сумме давали число меньшее или равное 30. И перебирая, смотреть чему равна сумма выбранных элементов первого. В идеале перебирать хотелось бы, не вообще все возможные комбинации элементов первого, а только те, которые бы удовлетворяли условию, что соотвествующие элементы второго в сумме будут меньше или равны 30.

[GAGArin]

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

Забыл сказать для N порядка 10 и выше это будет весьма долго. Если отсечение не будет происходить ближе к началу (не знаю уж какая там точно задача)

[Константин Н.]

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

[GluKoBuG]

Люди! Я не совсем понял вопрос.
Короче, как я понял:

Код: Выделить всё


Dim c1 As Integer
Dim c2 As Integer
For c1=0 to 'Размер массива 1
For c2=0 to 'Размер массива 2
If massive1(c1)=massive2(c2) Then
'Твои условия
end if
next
next


2.

Код: Выделить всё


Dim с As Integer
For c=0 To 'размер массива
If massive1(c)+massive2(c)<=30 Then
'Твои условия
end if
next


3. Что такое рекурсия?
Это когда действие возвращается к самому себе при невыполнении какого-то условия

Код: Выделить всё


Private Sub rec()
dim i as integer
l:
i=i+1
If i<=15 then GoTo l
end sub

[hCORe]

Рекурсия - это вызов функцией самой себя. Алгоритм быстрой сортировки - самый яркий пример.

НО! Нужно четко знать, когда рекурсия полезна, когда - нет. Например, для подсчета чисел в последовательности Фибоначчи она не подходит по определению, лучше итеративный способ; а в случае с быстрой сортировкой итеративный метод, наоборот, проигрывает.

[GluKoBuG]

Рекурсия - это вызов функцией самой себя. Алгоритм быстрой сортировки - самый яркий пример.

НО! Нужно четко знать, когда рекурсия полезна, когда - нет. Например, для подсчета чисел в последовательности Фибоначчи она не подходит по определению, лучше итеративный способ; а в случае с быстрой сортировкой итеративный метод, наоборот, проигрывает.

С рекурсией поосторожней: советую сохранить все данные до запуска...
При неправильном построении может повиснуть...

Код: Выделить всё


Sub p()
Dim i As Integer
i=i-1
If i<10 Then p
end sub

В таком случае советую нажать CTRL+Pause или дождаться сообщения о ошибке

[GAGArin]

Ну вроде нужен полный перебор. Как тут без рекурсии не особо знаю.
Ну типа того

Код: Выделить всё


Sub Perebor(combination as string, sum as integer)
  if sum <30 then
    for t=1 to N
      Perebor(combination & ";" & FirstArr(t),sum+SecArray(t))
      'Тут сам дорабатывай если не надо повторений одних и тех же значений
    next t
  Else
    MsgBox Combination
  end if
end sub

Ну и вызвать Perebor("",0)

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

Не тестируй на массивах длиннее 7-8 элементов!!!

[Константин Н.]

Народ!)) Порывшись некоторое время в интернете (второй день уже) я узнал, что моя задача обычно называеться "Задача об укладке рюкзака". Даже нашел некоторые исходники, жаль только, что на паскале а не на басике. Как пишут, абсолютно точное решение задачи проще всего получить методом полного перебора. Но я не совсем понимаю как его сделать "по-умному", то есть, не просто взять все возможные сочетания и посчитать значения сумм и веса (в таком случае и правда многовато их выйдет). К тому же в методичке особо отмечено, что надо уделить внимание прекращению перебора, как только станет ясно, что он не представляет в дальнейшем интереса. Или может кто-либо просто знает ссылку где эта задача уже разобрана в общем виде для VB?

[GAGArin]

Постом выше Там вроде практически полностью готовое к употреблению решение.

Первая проверка sum < 30 и есть отсечение. Если переложили эта ветка рекурсии отомрет. Как раз то про что пишут в методичке.

А если нужно какое-то частное решение, то описывай задачу подробнее. Что конкретно нужно. Может получится обойтись без перебора.