Как найти оптимальную сумму?

Question

[Артем Кондрацкий]

Здравствуйте, помогите мне понять. Есть массив чисел, надо найти два числа, сумма которых не превышает n.
Пример:
arr = [5, 3, 8, 10]
n = 15
логичнее взять 5 и 10

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

Comments

[krka92]

5+3, 3+8, 8+3 тоже не превышают 15. Или нужно найти максимально возможную сумму не превышающую n?

Answer 1

[Иван Мельников]

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

Answer 2

[Руслан .]

1. Сортируем массив по убыванию.
[5, 3, 8, 10] -> [10, 8, 5, 3]
2. Находим первый элемент массива не превышающий n - amin (amin - последний элемент массива, он же минимальный)
Это i = 0 и a[i] = 10 (не превышает 15-3 = 12)
3. Идем от найденного элемента к концу массива (j = i+1...len(a)-1) и берем первый элемент j для
которого выполняется условие a[i] + a[j] <= n.
В вашем случае j = 2 и a[j] = 5.
4. Сохраняемой найденное как промежуточный результат i_cur=i,j_cur=j,sum_cur=a[i] + a[j].
5. Если на предыдущем шаге уже был найден sum_cur, то сравниваем его с текущим и выбираем тот, который больше.
6. Далее, если a[i]+a[i+1]>=sum_cur, то продолжаем с пункта 3 только i=i+1.
7. Если попали сюда, а sum_cur не определён, то решения нет.

Comments

[Roman K]

Успокойся, синьор))

[Руслан .]

Думаете легко писать с телефона :)

Answer 3

[Developer]

Много if заменяются циклами

Comments

[Артем Кондрацкий]

ну это понятно
типо того?

for i in range(1, len(arr)):
  if (arr[1] + arr[i] <= n):
    break

[Developer]

Артем Кондрацкий, только в данном случае два цикла - один вложен в другой

[Slavik KENNY]

логичнее взять 5 и 10

Не могу понять вашу логику в данном случае.
Условию удовлетворяют все варианты кроме 10 и 8, даже первые два числа 5+3 уже меньше 15, чем это вас не устроило?
Может имелось ввиду, что вам надо найти максимальную сумму не превышающую определенное условие?

Тогда да, вам правильно сказали - два цикла, перебор всех вариантов с проверкой максимальной суммы на условия: 1 - сумма меньше указанной, 2 - сумма больше прошлой найденной, тогда вы и узнаете максимально возможную сумму.

[Артем Кондрацкий]

Вячеслав Новиков, да, нужна максимальная сумма не превышающая значение n

[Never Ever]

Вячеслав Новиков, да и задача слегка напоминает про "рюкзак"
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

[Roman K]

Never Ever, нет, это далеко не рюкзак. Задача упрощается тем, что нужно найти пару элементов, а это всего лишь n^2 сложность. Тут простые два вложенных цикла