, если нам даны пары целых чисел (a1,b1),(a2,b2),(a3,b3),..(an,bn) и есть максимальное значение суммы = X, то как мы можем выбрать заданные пары таким образом, чтобы сумма первых записей (то есть a1, a2, .. ap) среди выбранных пар - maximum but <= X? Например, если данные пары составляют (43,9),(57,12),(13,4), а максимальная сумма составляет 71, тогда пары, которые мы можем выбрать, - (57,12) и (13,4), давая максимальную сумму < = 71 (X) как 70. Мой первоначальный подход заключается в сортировке пар на основе первых значений ввода в порядке убывания, а затем, возможно, алгоритме O (n^2). Но я не уверен в этом, и он также может быть слишком медленным для большого количества данных. Так есть ли эффективный подход к нему? Спасибо.Выбирая целые числа, чтобы максимизировать сумму
ответ
Похоже, это может быть реализовано с модификацией проблемы 0-1 Knapsack.
Спасибо, что общая сложность будет O (n^2), я думаю. – pranay
Я считаю, что это будет O (nX), который может быть O (n^2), если n == X – smang
Сложность будет зависеть также от значений n целых чисел, так как (100,2) (201,2) (350,7) с X = 95, выполняли бы очень мало работы с использованием меморизованной рекурсивной версии. – Xantix
- 1. Максимизировать сумму нескольких ведер?
- 2. Максимизировать сумму с лимитом
- 3. Python, чтобы подытожить целые числа списка
- 4. Scanf, чтобы найти целые числа
- 5. найти лучшую соседнюю пару, чтобы максимизировать сумму первого элемента.
- 6. Отрицательные целые числа> Положительные целые числа?
- 7. Дать регулярное выражение, чтобы захватить целые числа
- 8. Как изменить целые числа, чтобы Дата R
- 9. Ограничить пользователя, чтобы ввести целые числа?
- 10. Regex, чтобы найти последовательные целые числа
- 11. Список ограничений, чтобы принимать только целые числа
- 12. Преобразование строки в целые числа
- 13. Дробный подсчет через целые числа
- 14. Как читать целые числа отдельно
- 15. Вынув только целые числа, чтобы подвести и создать средний питона
- 16. Python Бесконечные целые числа
- 17. Средние случайные целые числа
- 18. Validate целые положительные числа
- 19. Сумма столбца, содержащего как десятичные числа, так и целые числа
- 20. Целые числа в JavaScript
- 21. Как проверить, содержит ли массив целые числа или целые числа
- 22. haxe: целые целые числа для абстрактных Int64
- 23. ifstream случайные целые числа?
- 24. Непрерывные целые числа
- 25. Целые числа, обозначающие 0?
- 26. Целочисленные целые числа
- 27. Целые числа в BASIC
- 28. Луа - Обнаружение целые числа
- 29. Случайные целые числа C++
- 30. Целые числа из строк
Я смущен, как максимальная сумма одновременно может быть X и <= X (если только ее просто X, в этом случае, почему существует user439407
i означает сумму первых записей должны быть максимальными, но в то же время 71 –
pranay
Я думаю, что «pranay'it - проблема динамического программирования. выполните некоторые поиски проблемы с максимальной суммой в динамическом программировании, которые могут вам помочь. но все же usouully в этом конкретном случае, который также даст O (n^2), но я думаю, что мы можем сделать это в O (n) примерно следующим образом: Сначала рассмотрим первую часть пары, как 43, 57 и 13, тогда как проблема планирования взвешенного интервала DP, т.е. u cn, получает soln of prob, например: «любое значение будет в решении, или оно не будет там, рекурсивное проектирование, так что решение будет либо i-м членом, либо от i-го члена –