Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

Нет изменений в размере, 16:58, 6 мая 2015
c=0 нет смысла рассматривать, так как тогда c/w[i]=0, внутренний цикл не будет выполняться.
Заполним <tex>d(0,c)</tex> нулями.
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 1 до <tex>W</tex>, по рекуррентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.
d[0][i] = 0;
for i = 1..N
for c = 01..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
Анонимный участник

Навигация