40
правок
Изменения
Отформатированы псевдокоды. Добавлено замечание, что метод динамического программирование всё равно не повзволяет решать задачу за п...
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.
Метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из NP-полных задач комбинаторной оптимизации.
== Реализация ==
Сначала генерируем <tex>A</tex>.
'''for ''' i = 0..W
A[0][i] = 0;
'''for ''' i = 0..N A[i][0] = 0; ''<font color="green">//Первые элементы приравниваем к 0</font>'' '''for ''' k = 1..N '''for ''' s = 1..W ''<font color="green">//Перебираем для каждого k все вместимости </font>'' '''if ''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); ''<font color="green">//выбираем класть его или нет</font>'' '''else ''' A[k][s] = A[k-1][s]; ''<font color="green">//иначе, не кладем</font>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s)
'''if ''' A[k][s] == 0 '''return'''; '''if ''' A[k-1][s] == A[k][s]
findAns(k-1, s);
'''else '''
findAns(k-1, s - w[k]);
ans.push(k);
=== Реализация ===
'''for ''' i = 0..W ''<font color="green">// база</font>''
d[0][i] = 0;
'''for ''' i = 1..N '''for ''' c = 1..W ''<font color="green">//Перебираем для каждого i, все вместимости </font>''
d[i][c] = d[i - 1][c];
'''for ''' l = min(b[i], c / w[i]) .. 1 ''<font color="green">// ищем l для которого выполняется максимум</font>''
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);
=== Реализация ===
sort(); ''<font color="green">// сортируем в порядке убывания удельной стоимости.</font>'' '''for ''' i = 1..N ''<font color="green">// идем по предметам </font>'' '''if ''' W >= w[i] ''<font color="green">//если помещается — берем</font>''
sum += p[i];
W -= w[i];
'''else''' sum += W / w[i] * p[i];''<font color="green">// иначе берем сколько можно и выходим</font>'' '''break''';
==Задача о суммах подмножеств==
