Блог пользователя Uzef

Автор Uzef, 11 лет назад, По-русски

Читаю одно из решений задачи о рюкзаке. Для задачи T(n,p) определим подзадачи T(i,j), i — количество начальных предметов, из которых делается выбор, j — максимум возможной суммарной массы уносимых предметов. Аргумент i задает количество предметов для подзадачи. Найдем рекуррентные соотношения для вычисления функции Т: T(0,0)=0, T(0,j)=0 при j>=1, T(i,0)=0 при i>=1. Если предмет с номером i остается на складе, то T(i,j)= T(i-1,j). Если предмет с номером i уносится со склада, то это уменьшает возможную суммарную массу для i-1 первых предметов на m[i], увеличивая значение решения на c[i]: T(i,j)= T(i-1,j-m[i]) + c[i]. Этот вариант возможен, если m[i] ≤ j. Из двух вариантов выбираем лучший.

Помогите пожалуйста детально разобраться с задачей на примере. Буду благодарен за помощь. Не могу понять: допустим у меня i=5 -это количество начальных предметов из которых делается выбор, j максимум возможной суммарной массы уносимых предметов выбранных из этих 5 предметов, то почему T(i,j)= T(i-1,j). Ведь если я не возьму один предмет, то и максимум суммы уносимых предметов должен уменьшиться. Что-то не могу понять логику задачи. Может кто-нибудь объяснит на языке понятном для ученика 8 класса. Заранее, спасибо за помощь.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Есть рюкзак, который выдерживает максимальную массу j. Если вы не взяли i-ый предмет, то вы в этот рюкзак ничего не положили, он остался пустым. А поэтому он по-прежнему выдерживает массу j :)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А если я положу предмет в рюкзак, то максимально возможная сумма рюкзака уменьшается на вес этого предмета. Так? Или останется по прежнему максимально допустимой.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, уменьшается на массу положенного в рюкзак предмета.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А если у меня уже есть куча предметов в рюкзаке, а i предмет я добавляю в него и максимальный допустимый вес рюкзака еще позволяет взять этот предмет, то всегда ли нам выгодно его положить в рюкзак, а может будет лучше вынуть какие нибудь три и заменить одним более ценным.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Если ты добавишь этот предмет к сумме A[I], то в массиве появится новая занятая ячейка(A[A[I]+то что мы доложили]). Но ячейка a[i] не удаляется. Она остается занятой, и может когда ты будешь рассматривать следующий предмет, ты тоже опять сможешь расмастривать сумму a[i] + данный новый предмет.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

давай рассмотрим перебор. i — номер предмета для которого мы делаем выбор брать его или не брать. j — оставшееся свободное место в рюкзаке.

int T(int i, int j) {
    if (j < 0)
        return -inf;
    if (i == -1)
        return 0;
    int res = T(i - 1, j);
    if (j >= m[i])
        res = max(res, T(i - 1, j - m[i]) + c[i]);
    return res;
}

...
int answer = T(n - 1, capacity);

очевидно рекурсивный перебор выше переберёт все возможные варианты положить в рюкзак некоторые предметы так, чтобы он не переполнился. Если добавить запоминание, то получим ДП описанное тобой выше.