Найти комбинацию чисел, сумма которых окажется максимально близкой к заданному числу - 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
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д