Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Uzef's blog

By Uzef, 11 years ago, In Russian

Читаю одно из решений задачи о рюкзаке. Для задачи 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 класса. Заранее, спасибо за помощь.

  • Vote: I like it
  • +8
  • Vote: I do not like it