Найти комбинацию чисел, сумма которых окажется максимально близкой к заданному числу - VB

Узнай цену своей работы

Формулировка задачи:

Помогите решить задачу. Дан ряд положительных чисел (пусть их сумма обозначается буквой P), и определённое значение (назовём N), которое несколько меньше суммы этих чисел (N<P). Нужно найти такие числа из ряда, которые дадут МАКСИМАЛЬНУЮ сумму, приближающуюся к N, но не превышают N (<=N). (Например, дан ряд чисел: 23, 35, 45, 21, 89, 73, 54, 49, 38, 18, 44, 63, сумма которых равна 552. И задано число 450. Нужно из заданного ряда выбрать те из чисел, сумма которых не превысит число 450, но при этом будет самой максимальной из всех возможных). Решение задачи необходимо для реализации на практике.

Решение задачи: «Найти комбинацию чисел, сумма которых окажется максимально близкой к заданному числу»

textual
Листинг программы
Sub Greedy(X() As Integer, S As Integer)
      '::: Сортируем массив
      n% = UBound(X, 1)
      For i% = 1 To n% - 1
          For j% = i% + 1 To n%
               If X(i%) > X(j%) Then
                  tmp% = X(i%)
                  X(i%) = X(j%)
                  X(j%) = tmp%
               End If
          Next j%
      Next i%
      '::: Cумма
      Q% = 0
      For i% = 1 To n%
          Q% = Q% + X(i%)
      Next i%
      '::: Первоначальный отбор
      For i% = 1 To n%
           Q% = Q% - X(i%)
           X(i%) = -X(i%)
           If Q% <= S Then Exit For
      Next i%
      '::: Если текущая сумма меньше нужной...
      '::: Пробуем добавить ранее отброшенные
      If Q% < S Then
         For i% = n% To 1 Step -1
             If X(i%) < 0 Then
                If Q% + Abs(X(i%)) <= S Then
                   X(i%) = Abs(X(i%))
                   Q% = Q% + X(i%)
                End If
                   
             End If
         Next i%
      End If
      '::: Печать
      Z% = 0
      For i% = 1 To n%
           If X(i%) > 0 Then
              Debug.Print X(i%)
              Z% = Z% + X(i%)
           End If
      Next i%
      Debug.Print "Сумма="; Z%
End Sub
 
Sub Test()
 
Dim X(1 To 11) As Integer
 
X(1) = 23
X(2) = 35
X(3) = 45
X(4) = 21
X(5) = 89
X(6) = 73
X(7) = 54
X(8) = 49
X(9) = 38
X(9) = 18
X(10) = 44
X(11) = 63
 
   Greedy X(), 450
 
End Sub

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 4 из 5
Похожие ответы