Задачка по программированию
Вычислить наиболее близкое к заданному числу Р возможное значение суммывот это я не понял....
есть ряд чисел
есть границы внутри ряда.
Нужно оценить сумму чисел внутри этих границ
Что такое Р и нах нужно? Что значит "сумма наиболее близкая к заданному числу Р?
Р - это искомая сумма что ли?
отрицательный числа, я так понимаю, есть?
Это задача практическая или нужен самый эффективный алгоритм поиска точного решения?
ну да, если неотрицательные, то можно за k log k: считаем суммы от 1 до j, идем по этому массиву, в хвосте ищем двоичным поиском место для s_j + P, вычисляем разницу, находим минимум. Если есть отрицательные — пока хз.
Да, это решение я тоже нашел. Только в нем есть ошибка, во фразе "Нам надо найти в этом массиве два элемента C[i] и C[j], значение разности которых наиболее близко к P". Нужно, чтобы в неотсортированном массиве было i < j, иначе C[j] - C[i] не будет A[i + 1] + ... + A[j]. Алгоритм же тупо сортирует C и ищет минимум по любым i, j.
Например, пусть A = [10, -3].
Тогда C = [0, 10, 7].
Отсортированный С = [0, 7, 10].
Пусть P = 3. Алгоритм в решении с радостью найдет C[3] - C[2] = 3, и, соответственно, выдаст ответ 0.
При этом правильный ответ будет 4.
Например, пусть A = [10, -3].
Тогда C = [0, 10, 7].
Отсортированный С = [0, 7, 10].
Пусть P = 3. Алгоритм в решении с радостью найдет C[3] - C[2] = 3, и, соответственно, выдаст ответ 0.
При этом правильный ответ будет 4.
Отрицательные могут быть. Задача олимпиадная, идеальная эффективность не нужна, нужно только, чтобы требования в условии выполнялись.
Задача олимпиадная, идеальная эффективность не нужнатут либо противоречие, либо необходимо явное ограничение на k и требуемое время работы. Короче, нужен наиболее эффективный алгоритм.
Да, это решение я тоже нашел. Только в нем есть ошибкаИзвините, поспешил. Не сообразил сразу, что A могут быть отрицательными.
Не, почему противоречие. Просто сказано, что сложность не должна быть O(n^2). Можно хоть O(n^1.999). Ну или O(n logn).
а это разве не NP?
вот выбрать подмножество, дающую максимальную сумму - точно NP.
а вот непрерывный отрезок... надо прикинуть
вот выбрать подмножество, дающую максимальную сумму - точно NP.
а вот непрерывный отрезок... надо прикинуть
конечно не NP, можно все эти отрезки перебрать за K^2 
А можно даже в лоб за K^3 (не подсчитывая аккумулированную сумму).
конечно не NPхотя если принимать во внимание нерешенность задачи NP=P, это заявление выглядит довольно смело
Например, пусть A = [10, -3].Это как будет 4? Там вроде сумма 4 никак не получается в этом массиве.
Тогда C = [0, 10, 7].
Отсортированный С = [0, 7, 10].
Пусть P = 3. Алгоритм в решении с радостью найдет C[3] - C[2] = 3, и, соответственно, выдаст ответ 0.
При этом правильный ответ будет 4.
разность суммы 10 и -3 и числа 3, я тоже не сразу понял, что за 4
Да, это решение я тоже нашел. Только в нем есть ошибка, во фразе "Нам надо найти в этом массиве два элемента C[i] и C[j], значение разности которых наиболее близко к P". Нужно, чтобы в неотсортированном массиве было i < j, иначе C[j] - C[i] не будет A[i + 1] + ... + A[j]. Алгоритм же тупо сортирует C и ищет минимум по любым i, j.Что мешает при поиске минимума откидывать варианты когда j>=i?
На правах зануды.
Конечно же она NP, что ты в своем посте и доказал:
Конечно же она NP, что ты в своем посте и доказал:
можно все эти отрезки перебрать за K^2
вы точно знаете, что такое NP? попробуйте доказать более качественно
ну позразумевалась NP-полная в исходном посте, очевидно, мы тут не теорией занимаемся, нам лишние слова писать некогда 
Оставить комментарий
vera_79
Народ, помогите решить следующую задачу:Дано положительное целое число К и К целых чисел А(1...,А(К). Вычислить наиболее близкое к заданному числу Р возможное значение суммы
S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N
где 1<=М<=N<=К.
Примечание. Число К столь велико, что числа А(1А(2 ..., А(К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К2 даже простейших операций не хватает времени.