Найти наибольшее количество слагаемых из переменных двух массивов?

Question

[emtyxd]

Существует 2 массива n, m
Переменная предела суммы s
Необходимо найти максимальное количество слагаемых из 2 массивов (n[0] + m[0]), брать числа можно только по порядку.
После нахождения суммы, которая равна или меньше переменной s, числа из массивов удаляются.
Например:
n = [5, 1, 1, 1, 1]
m = [1, 3, 3, 3, 3]
s = 10
Предполагаемый результат 6 ( n[0] + n[1-4] + m[1] / (5 + 1 + 1 + 1 + 1 +1) )

Comments

[emtyxd]

Есть набросок кода, но он сравнивает первые числа массивов, не заглядывая дальше.

n, m, s = [int(i) for i in input().split(" ")]
arr_n, arr_m = [], []
result = 0


for _ in range(max(n, m)):
    a, b = input().split(" ")
    if a != '-':
        arr_n.append(int(a))
    if b != '-':
        arr_m.append(int(b))


suma = min(arr_n[0], arr_m[0])
while suma <= s:
    print(arr_n, arr_m)
    if arr_n[0] < arr_m[0]:
        suma += arr_n[0]
        arr_n.pop(0)
    else:
        suma += arr_m[0]
        arr_m.pop(0)
    result += 1

print(result)

[Алан Гибизов]

emtyxd, признаться, я вообще не понимаю, что нужно сделать. Попробуйте забыть, что вы делали и думали, и прочтите свой вопрос свежим взглядом и подумайте, что буквально там сказано сделать?
Найти «максимальное количество слагаемых». Это вообще что?

[Модератор]

Название вопроса надо формулировать корректно, по правилам русского языка. Сейчас на название вопроса ответ может быть только «да», «нет» и «не знаю».

Answer 1

[Alexandroppolus]

function maxCount(s, a1, a2, i1 = 0, i2 = 0) {
    const c1 = i1 < a1.length && a1[i1] <= s ? 1 + maxCount(s - a1[i1], a1, a2, i1 + 1, i2) : 0;
    const c2 = i2 < a2.length && a2[i2] <= s ? 1 + maxCount(s - a2[i2], a1, a2, i1, i2 + 1) : 0;

    return Math.max(c1, c2);
}

console.log(maxCount(10, [5, 1, 1, 1, 1], [1, 3, 3, 3, 3]));

на каждом шаге выбираем максимум из с1 (случай, когда можно взять очередной элемент из массива a1) и с2 (из массива а2)

можно добавить мемоизацию для ускорения (мемоизовать по паре i1, i2)

Comments

[Alexandroppolus]

Хотя можно проще сделать. Сначала набрать числа только из первого массива (в рамках лимита).
Потом на каждом шаге отбрасывать очередное число из первого массива, донабирать из второго, смотреть сколько получилось.
Это позволит решить задачу без рекурсии, без дополнительной памяти и за линейное время.

Answer 2

[Алан Гибизов]

Найти наибольшее количество слагаемых из переменных двух массивов?

Не найти.

Comments

[emtyxd]

Алан, спасибо за ваш ответ. Теперь я прозрел и понял что такое невозможно.

Например:
n = [5, 1, 1, 1, 1]
m = [1, 3, 3, 3, 3]
s = 10
Предполагаемый результат 6 ( n[0] + n[1-4] + m[1] / (5 + 1 + 1 + 1 + 1) )

[AVKor]

Мне тоже не нужно находить. Тем более что неясно, что вообще искать.

[Алан Гибизов]

emtyxd, приведенный результат, по-вашему, есть «количество слагаемых»?

[emtyxd]

Нужно найти количество слагаемых из 2 массивов n и m, сумма этих слагаемых не должна превышать s. Загвоздка в том, что из массивов можно брать числа только по порядку.

[emtyxd]

Алан Гибизов, вы меня простите, но что тогда по вашему число 6.

[Алан Гибизов]

emtyxd, это число 6.

Задача ваша поставлена очень и очень криво. Оттого очень сложно понять, что же надо делать.
Рекомендую переформулировать задачу так, будто вы объясняете ее дошколенку.