Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

int 
i = items.size(); i > 0; i--) { // идем в обратном направлении
// этот предмет уже выбран?
if 
(table[i — 1][capacity] != table[i][capacity]) {
solution.add(items.get(i — 1));
// если предмет выбран, то вычитаем его вес
capacity -= items.get(i — 1).weight;
}
}
return 
solution;
}
Внутренний.цикл.в.первой.части.этой.функции.будет.выполняться.
NC
.раз,.
где.
N
.—.количество.предметов,.а.
C
.—.максимальная.вместимость.рюкзака..
Следовательно,.алгоритм.выполняется.за.время.
O
(
NC
),.что.для.большого.ко-
личества.предметов.значительно.лучше,.чем.метод.грубой.силы..Например,.для.
11.описанных.далее.предметов.с.помощью.алгоритма.грубой.силы.мы.должны.
были.рассмотреть.2
11
,.или.2048.комбинаций..Представленная.ранее.функция.
динамического.программирования.будет.выполняться.825.раз.(11.·.75),.посколь-
ку.максимальная.вместимость.рюкзака.составляет.в.данном.случае.75.произ-
вольных.единиц..Эта.разница.будет.расти.экспоненциально.по.мере.увеличения.
количества.предметов.
Давайте.посмотрим.на.решение.в.действии.(листинг.9.3).
Листинг 9.3. 
Knapsack.java (продолжение)
public static void 
main(String[] args) {
List items = 
new 
ArrayList<>();
items.add(
new 
Item("television", 50, 500));
items.add(
new 
Item("candlesticks", 2, 300));
items.add(
new 
Item("stereo", 35, 400));
items.add(
new 
Item("laptop", 3, 1000));
items.add(
new 
Item("food", 15, 50));
items.add(
new 
Item("clothing", 20, 800));
items.add(
new 
Item("jewelry", 1, 4000));
items.add(