Sudhirsd Ответов: 3

Как найти возможную уникальную комбинацию числа множества где сумма меньше чем равна чему то


например
мой список пунктов=2,3,4,5,6,7,8,9,10
суммирование цели=30
элемент в наборе=5

выход, как:-

23456,34567,96541, ........, ......
каждый набор должен быть уникальным

и такое же количество не следует повторять

например, 22345 - это неправильно... но 2-это два раза в списке элементов, тогда это правильно.

Что я уже пробовал:

Dim finalList As New List(Of List(Of Object))
i -= 1
'Add the objects to the first sub list.
Dim indexs(k - 1) As Integer
Dim firstSubList As New List(Of Object)
For j As Integer = 0 To k - 1
    indexs(j) = j
    firstSubList.Add(items(j))
Next
'Add the first sub list to the parent list.
finalList.Add(firstSubList)
'Continue adding lasts.
While indexs(0) <> n - k AndAlso finalList.Count < 2147483647
    If indexs(i) < i + (n - k) Then
        indexs(i) += 1
        Dim subList As New List(Of Object)
        For Each j As Integer In indexs
            'Add the objects to the sub list.
            subList.Add(items(j))
        Next
        'Add the sub list to the parent list.
        finalList.Add(subList)
    Else
        Do
            i -= 1
        Loop While indexs(i) = i + (n - k)
        indexs(i) += 1
        For j As Integer = i + 1 To k - 1
            indexs(j) = indexs(j - 1) + 1
        Next
        Dim subList As New List(Of Object)
        For Each j As Integer In indexs
            'Add the objects to the sub list.
            subList.Add(items(j))
        Next
        'Add the sub list to the parent list.
        finalList.Add(subList)
        i = k - 1
    End If
End While

Patrice T

В чем проблема с этим кодом ?

3 Ответов

Рейтинг:
2

Maciej Los

В дополнение к решению №1 от OriginalGriff у меня есть для вас небольшой совет: Вы должны получить количество комбинаций без повторений, чтобы иметь возможность создать 2d-массив из 5-элементных чисел.

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

Пример: рисование 6 чисел (k) от 49 лет (n) (лото), сколько фишек можно получить? Цифры не могут повторяться, и порядок не имеет значения. Результат: 1, 3, 12, 34, 45, 46 это то же самое, что и результат: 3; 12; 45; 1; 46; 34

Cwor = нк = n!/k!(н - к)! = 9!/5!(9-5)! = 362880/120 * 24 = 362880/2880= 126


Вывод: Результирующий набор должен быть массивом из 5 элементов, который насчитывает 126 уникальных подмножеств.


Рейтинг:
1

Patrice T

Цитата:
Как найти возможную уникальную комбинацию числа множества где сумма меньше чем равна чему то

Насколько я вижу, этот код не связан с требованием.
Вы притворяетесь, что работаете над этим требованием ?

Решение этой проблемы похоже на решение большинства проблем.
Возьмите лист бумаги, карандаш и решите задачу вручную механическим способом.
Механический способ решения проблемы-это в основном ваш алгоритм.
 2 3 4 5 6 7 8 9 10
 x x x x x          sum is ..
 x x x x   x        sum is ..
 x x x x     x      sum is ..
...


Рейтинг:
0

OriginalGriff

Начните с сортировки данных, чтобы убедиться, что они упорядочены, а затем работайте с самой низкой цифры вверх. (Строго говоря, это не обязательно, но позволяет быстрее устранять целые ветви.)
Но нет такой вещи, как уникальная комбинация из 5 значений из этого набора, которая суммируется меньше или равна 30; есть много решений:

2 + 3 + 4 + 5 + 6  = 20
2 + 3 + 4 + 5 + 7  = 21
2 + 3 + 4 + 5 + 8  = 22
2 + 3 + 4 + 5 + 9  = 23
2 + 3 + 4 + 5 + 10 = 24
2 + 3 + 4 + 6 + 7  = 22
2 + 3 + 4 + 6 + 8  = 23
...
Если вы ищете ровно 30, то есть также несколько решений:
2 + 3 + 6 + 9 + 10 = 30
2 + 3 + 7 + 8 + 10 = 30
2 + 4 + 5 + 9 + 10 = 30
...
Так что вы должны быть готовы найти несколько комбинаций.
Подумайте о том, как бы вы сделали это вручную, а затем напишите себе рекурсивный метод для их обработки - это не сложно, когда вы об этом думаете: начните с "первого" элемента, а затем найдите все комбинации, используя только те, что справа. Если вы передадите цель и количество цифр, разрешенных методу вместе с текущим индексом, это будет довольно просто, как только вы поймете, что такое рекурсия - а именно этого хочет от вас ваш наставник!

Это твое домашнее задание, а не мое - так что я не дам тебе никакого кода! Просто не забудьте хорошенько подумать и использовать отладчик, чтобы точно определить, что происходит с вашим кодом.
Попробуйте - с небольшим усилием вы доберетесь туда!