Читаю одно из решений задачи о рюкзаке. Для задачи 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 класса. Заранее, спасибо за помощь.
Есть рюкзак, который выдерживает максимальную массу j. Если вы не взяли i-ый предмет, то вы в этот рюкзак ничего не положили, он остался пустым. А поэтому он по-прежнему выдерживает массу j :)
А если я положу предмет в рюкзак, то максимально возможная сумма рюкзака уменьшается на вес этого предмета. Так? Или останется по прежнему максимально допустимой.
Да, уменьшается на массу положенного в рюкзак предмета.
А если у меня уже есть куча предметов в рюкзаке, а i предмет я добавляю в него и максимальный допустимый вес рюкзака еще позволяет взять этот предмет, то всегда ли нам выгодно его положить в рюкзак, а может будет лучше вынуть какие нибудь три и заменить одним более ценным.
Если ты добавишь этот предмет к сумме A[I], то в массиве появится новая занятая ячейка(A[A[I]+то что мы доложили]). Но ячейка a[i] не удаляется. Она остается занятой, и может когда ты будешь рассматривать следующий предмет, ты тоже опять сможешь расмастривать сумму a[i] + данный новый предмет.
давай рассмотрим перебор. i — номер предмета для которого мы делаем выбор брать его или не брать. j — оставшееся свободное место в рюкзаке.
очевидно рекурсивный перебор выше переберёт все возможные варианты положить в рюкзак некоторые предметы так, чтобы он не переполнился. Если добавить запоминание, то получим ДП описанное тобой выше.