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

new 
Item("books", 100, 300));
items.add(
new 
Item("printer", 18, 30));
items.add(
new 
Item("refrigerator", 200, 700));

---

9.1. Задача о рюкзаке
247
items.add(
new 
Item("painting", 10, 1000));
List toSteal = 
knapsack
(items, 75);
System.
out
.println("The best items for the thief to steal are:");
System.
out
.printf("%-15.15s %-15.15s %-15.15s%n", "Name", "Weight", 
"Value");
for 
(Item item : toSteal) {
System.
out
.printf("%-15.15s %-15.15s %-15.15s%n",
item.name, item.weight, item.value);
}
}
}
Если.вы.проверите.результаты,.выведенные.в.консоль,.то.увидите,.что.опти-
мальными.предметами,.которые.можно.взять,.являются.картина,.украшения,.
одежда,.ноутбук,.стереосистема.и.подсвечники..Вот.пример.выходных.данных,.
показывающий.наиболее.ценные.для.вора.вещи.с.учетом.того,.что.вместимость.
рюкзака.ограниченна:
The best items for the thief to steal are:
Name Weight Value
painting 10 1000.0
jewelry 1 4000.0
clothing 20 800.0
laptop 3 1000.0
stereo 35 400.0
candlesticks 2 300.0
Чтобы.лучше.понять,.как.это.все.работает,.рассмотрим.некоторые.особенности.
функции.
knapsack()
:
for 
(
int 
i = 0; i < items.size(); i++) {
Item item = items.get(i);
for 
(
int 
capacity = 1; capacity <= maxCapacity; capacity++) {
Для.каждого.возможного.количества.предметов.мы.перебираем.в.цикле.все.
варианты.вместимости.рюкзака.вплоть.до.максимальной..Обратите.внимание.
на.то,.что.я.говорю.«каждое.возможное.количество.предметов»,.а.не.«каж-
дый.предмет»..Когда.
i
.равно.2,.это.означает.не.просто.предмет.номер.2,.а.все.
возможные.комбинации.из.первых.двух.предметов.для.каждой.исследуемой.
вместимости..
item
.—.это.следующий.из.рассматриваемых.предметов,.который.
можно.украсть: