Алгоритм: максимизировать сумму подмассива, чтобы общая сумма не превышала максимум [закрыто] ⇐ C++
-
Гость
Алгоритм: максимизировать сумму подмассива, чтобы общая сумма не превышала максимум [закрыто]
Мне нужно написать алгоритм, который кажется простым, но я не могу найти способ сделать это (как и не могу найти алгоритм, который уже это делает). Входные данные представляют собой упорядоченный массив целых чисел и одно целое число с именем «max». Выходные данные представляют собой подмассив входного массива, поэтому сумма значений в этом подмассиве максимальна, но не превышает входную переменную «max».
Пример:
Ввод: [7000, 7000, 6000, 6000, 5000, 5000], 18010
Выход: [7000, 6000, 5000].
Выходная сумма равна 18 000. Это лучшее решение, поскольку не существует другого подмассива с суммой 18 000 < sum
Мне нужно написать алгоритм, который кажется простым, но я не могу найти способ сделать это (как и не могу найти алгоритм, который уже это делает). Входные данные представляют собой упорядоченный массив целых чисел и одно целое число с именем «max». Выходные данные представляют собой подмассив входного массива, поэтому сумма значений в этом подмассиве максимальна, но не превышает входную переменную «max».
Пример:
Ввод: [7000, 7000, 6000, 6000, 5000, 5000], 18010
Выход: [7000, 6000, 5000].
Выходная сумма равна 18 000. Это лучшее решение, поскольку не существует другого подмассива с суммой 18 000 < sum
