1

Условие: Есть массив целых чисел N и есть число P. Вопрос: как найти индексы элементов N такие, чтобы сумма ΣN(i) была максимально приближена к P.

Например, N = [2, 5, 8] и P = 11. Правильный ответ будет 10 = 8 + 2.

Каким способом кроме перебора можно решить эту задачу?

4
  • Граничные условия надо добавить если P больше суммы всех элементов или меньше минимального элемента массива задача превращается в фарс.
    – igumnov
    7 фев 2013 в 14:12
  • С ходу могу предложить очень медленное костыльное решение. Берете этот код geeksforgeeks.org/find-subarray-with-given-sum Применяете его к каждой перестановке исходного массива. Если он ничего не находит уменьшаете входное число P на единицу и снова повторяете до тех пор пока не найдете нужный массив.
    – igumnov
    7 фев 2013 в 14:21
  • Если я не ошибаюсь, ваша задача совсем немного отличается от knapsack problem.
    – VladD
    7 фев 2013 в 14:24
  • igumnov, вы правы, граничные условия и правда не помешают! Спасибо за предложенное решение, но P в моём случае достаточно большое число, порядка десятков тысяч, и уменьшать на единицу каждый раз будет горячкой. VlaD, и правда, разберу статью, спасибо за ссылку! 7 фев 2013 в 17:21

2 ответа 2

2

Частный случай задачи об укладке рюкзака (вес и ценность предметов одинакова) вики.

1
  • Да, это действительно оказалась укладка рюкзака :) @VladD @igumnov спасибо вам за ценные советы, они мне очень помогли! 8 фев 2013 в 9:10
0

Стандартная задача на динамическое программирование

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.