Как найти максимальную сумму в массиве меньше N - PullRequest
Новая
       31

Как найти максимальную сумму в массиве меньше N

0 голосов
/ 28 января 2020

У меня есть массив из M элементов. Я должен найти максимальную сумму моего массива, которая меньше целого числа "N". Все элементы в массиве являются натуральными числами, большими или равными нулю. Кроме того, сумма может быть непоследовательной.

Например: скажем, M is = [1,2,3,6,0, 8, 9, 12] и N = 20, поэтому здесь ответ 20

, но если M = [1,5,4,6] и N = 13, ответ 12 - максимальная сумма массива, которая меньше N

Ответы [ 3 ]

0 голосов
/ 28 января 2020

Сначала нам нужно проверить, меньше ли сумма чисел, чем N, а затем сохранить сумму как результат и сумму как строку в разных списках одновременно.

Поэтому, когда мы находим максимум в списке сумм меньше N, мы можем получить доступ ко второму списку, содержащему строки, используя тот же индекс. 

M = [12, 9, 8, 4, 8, 5]
Ma = []
Ma_num = []
N = 20
for i in M:
    for a in range(len(M)):
        if i + M[a] <= N:
            Ma.append(f"{i} + {M[a]}")
            Ma_num.append(i + M[a])
max_num = Ma_num.index(max(Ma_num))


print(Ma[max_num])

Вывод: 

12 + 8

Кстати, если вы означало, что вы хотели видеть число 20 в выводе, решение таково: 

M = [12, 9, 8, 4, 8, 5]
Ma = []
N = 20
for i in M:
    for a in range(len(M)):
        if i + M[a] <= N:
            Ma.append(i + M[a])
max_num = max(Ma)
print(max_num)

Вывод: 

20
0 голосов
/ 28 января 2020

Это можно решить как Задача о ранце

В задаче о ранце у нас есть вектор значений (val) и весов (wt)

Мы хотим максимизировать сумму подмножества значений (val) таким образом, чтобы

соответствующий вес был меньше некоторого максимума (называемого емкостью)

Мы можем использовать алгоритм ранца следующим образом:

(1) Разрешение входного массива соответствует как весам, так и значениям

(2) Максимальная емкость - это максимальная сумма

Код для решения ранца отсюда 

def knapSack(W , wt , val, n): 

    # Base Case 
    if n == 0 or W == 0 : 
        return 0

    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 

    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
                   knapSack(W , wt , val , n-1)) 

def max_sum(K, arr):
  '''Solve using Knapsack code with (set weights and values equal to arr)'''
  return knapSack(K, arr, arr, len(arr))

Тест 

arr = [1,5,4,6]
print(max_sum(13, arr))
#>>> Outputs 12

arr =[1,2,3,6,0, 8, 9, 12]
print(max_sum(20, arr))
#>>> Outputs 20

arr =  [2,5,6,8]
print(max_sum(17, arr))
#>>> Outputs 16

Сложность

Временная сложность решения ранца составляет O (nW)

где n - длина массива arr

W - максимальная сумма

0 голосов
/ 28 января 2020

У меня есть решение, сначала сложите все числа в вашем массиве m, затем в al oop проверьте

sum> = n, если true верните m иначе sum = m - min (m) и удалите min и проверьте еще раз

############################## 3

проверьте это решение 

M = [1,2,3,6,0, 8, 9, 12]
n = 20
s= 0

while s < n:
    maximum = max(M)
    M.remove(maximum)
    if (s+ maximum)>n:
        continue
    s = s + maximum
print(s)
...