Введение
Продолжаю свой крестовый поход по NP-полным задачам. От судоку и латинских квадратов немного устал, потому давеча решил переключиться на что-то другое. Выбор пал на задачу о рюкзаке, которая звучит следующим образом, цитата из Вики.
Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
Решение "навскидку" было найдено очень быстро и, честно говоря, после истории с судоку и латинским квадратом процесс показался детским утренником. Не уверен в том, рабочий ли алгоритм на 100 процентов, но, по крайней мере, все тест-кейсы, что были мной придуманы решаются на раз. Потому буду рад, если кто-нибудь поможет разобраться в этом вопросе подкидыванием каких-нибудь новых и более хитрых кейсов, дабы проверить решение на "вшивость".
Сразу прикладываю реп. Как всегда Java, я ж джавист все-таки)
Теперь к делу.
Еще раз формулировка задачи и суть алгоритма
Дан некий контейнер размерностью W. Дано множество элементов, каждый из которых имеет свойства "цена" и "вес". Необходимо во множестве элементов найти такое подмножество, которое имеет максимальную суммарную цену с соблюдаемым ограничением "суммарный вес <= W".
Суть придуманного мной алгоритма проста, как пять копеек: мы находим все возможные и как можно более длинные варианты наполнения (поясню ниже), которые укладываются в ограничение на размер контейнера. Затем мы находим то наполнение, которое имеет максимальную суммарную цену среди полученных. На этом все.
Иллюстрация на примере. Вместимость контейнера (W) = 9.
ВЕС | ЦЕНА |
1 | 4 |
2 | 3 |
7 | 2 |
3 | 1 |
8 | 6 |
В данном случае все возможные и как можно более длинные варианты наполнения выглядят так:
1 + 2 + 3 = 6
1 + 7 = 8
1 + 8 = 9
2 + 7 = 9
Понятно, что нам нет смысла учитывать отдельно 1, 1 + 2, 1 + 3 и так далее - это подмножества как минимум одного из приведенных вариантов наполнения. Это и заставляет приведенное множество наполнений гордо именоваться всеми возможными и как можно более длинными вариантами наполнения.
upd: как показала практика - смысла-то может быть и не имеет, но алгоритм их отсеивания слишком дорог и нерентабелен. Так что в конечном наборе все-таки будет, например, 2 + 3 на таком кейсе и прочее. Но суть в том, что потенциальное решение будет именно в рамках приведенного множества вариантов наполнения.
Теперь среди этих наполнений достаточно найти то наполнение, что имеет максимальную суммарную цену. В нашем случае нетрудно убедиться, что это будет 1 + 8, и общий профит у нас - 10. Предметы с такими весами мы с чистой совестью упаковываем.
В общем-то это и есть вся суть алгоритма. Давайте рассмотрим мою реализацию на Java.
Реализация
Начинаем, разумеется, с интерфейса нашего "рюкзака".
package com.smolka.backpack;
import java.util.Set;
public interface Backpack {
void fillBackpack(Set<Item> items);
Set<Item> getItemsInBackpack();
int getCapacity();
int getCostOfContent();
int getWeightOfContent();
}И класса предметов.
package com.smolka.backpack;
import java.util.Objects;
public class Item {
private final String id;
private final int weight;
private final int cost;
public Item(String id, int weight, int cost) {
assert weight > 0;
assert cost > 0;
this.id = id;
this.weight = weight;
this.cost = cost;
}
public String getId() {
return id;
}
public int getWeight() {
return weight;
}
public int getCost() {
return cost;
}
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
Item item = (Item) o;
return Objects.equals(id, item.id);
}
@Override
public int hashCode() {
return Objects.hashCode(id);
}
}Ключевой метод в Backpack - fillBackpack, который и попытается как можно выгодней запаковать наш рюкзак переданными элементами. Остальные - по большей части вспомогательный сахар, позволяющий посмотреть на то, что у нас вышло по цене, весу и самому наполнению рюкзака.
В предметы, как видно, я решил добавить поле id - уникальный идентификатор предмета. Как по мне, так будет более наглядно и во входном множестве будут содержаться элементы с одинаковым сочетанием цены и веса. Но можно было бы обойтись просто составным ключом weight + cost, если условия задачи не будут подразумевать таких повторов. В моем случае пусть будет первое.
Реализация такова.
Реализация
package com.smolka.backpack.impl;
import com.smolka.backpack.Backpack;
import com.smolka.backpack.Item;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
public class BackpackImpl implements Backpack {
private final Set<Item> itemsInBackpack;
private final int capacity;
public BackpackImpl(int capacity) {
assert capacity > 0;
this.itemsInBackpack = new HashSet<>();
this.capacity = capacity;
}
@Override
public void fillBackpack(Set<Item> items) {
itemsInBackpack.clear();
List<Item> preProcessedItems = preProcessItems(items);
List<ItemSelectionResult> selectionResults = new ArrayList<>();
for (int i = 0; i < preProcessedItems.size(); i++) {
addSelectionResultForIndex(i, preProcessedItems, selectionResults);
}
int maxCost = -1;
List<Item> branchWithMaxCost = new ArrayList<>();
for (ItemSelectionResult selectionResult : selectionResults) {
if (selectionResult.isEmpty()) {
continue;
}
ItemsCostInfo itemsCostInfo = selectionResult.getBranchWithMaxCost();
int currentCost = itemsCostInfo.cost();
if (currentCost > maxCost) {
maxCost = currentCost;
branchWithMaxCost = itemsCostInfo.items();
}
}
itemsInBackpack.addAll(branchWithMaxCost);
}
@Override
public int getCostOfContent() {
return itemsInBackpack.stream().map(Item::getCost).reduce(Integer::sum).orElse(0);
}
@Override
public int getWeightOfContent() {
return itemsInBackpack.stream().map(Item::getWeight).reduce(Integer::sum).orElse(0);
}
@Override
public Set<Item> getItemsInBackpack() {
return itemsInBackpack;
}
@Override
public int getCapacity() {
return capacity;
}
private List<Item> preProcessItems(Set<Item> items) {
Set<Item> itemsWithoutOverWeightedElements = items.stream().filter(item -> item.getWeight() <= capacity).collect(Collectors.toSet());
Map<Integer, WeightSequenceInfo> weightSequenceInfoMap = new HashMap<>();
for (Item item : itemsWithoutOverWeightedElements) {
int weight = item.getWeight();
weightSequenceInfoMap.putIfAbsent(weight, new WeightSequenceInfo(weight));
weightSequenceInfoMap.get(weight).addItem(item);
}
List<Item> preProcessedItemsList = new ArrayList<>();
for (WeightSequenceInfo weightSequenceInfo : weightSequenceInfoMap.values()) {
preProcessedItemsList.addAll(weightSequenceInfo.getMostProfitablePossibleSequence(capacity));
}
preProcessedItemsList.sort(Comparator.comparingInt(Item::getWeight));
return preProcessedItemsList;
}
private void addSelectionResultForIndex(int index, List<Item> items, List<ItemSelectionResult> otherResults) {
ItemSelectionResult result = new ItemSelectionResult(items.get(index));
for (int i = index + 1; i < items.size(); i++) {
Item nextItem = items.get(i);
int newWeight = result.getLastBranch().getWeight() + nextItem.getWeight();
if (newWeight > capacity) {
Branch newBranch = result.createCapableBranchFromLast(nextItem, capacity);
if (newBranch.isEmpty()) {
otherResults.add(result);
return;
}
result.addNewBranch(newBranch);
} else {
result.addInLastBranch(nextItem);
}
}
otherResults.add(result);
}
private static class WeightSequenceInfo {
private final int weight;
private final List<Item> elements;
public WeightSequenceInfo(int weight) {
this.weight = weight;
this.elements = new ArrayList<>();
}
public void addItem(Item item) {
assert item.getWeight() == weight;
elements.add(item);
}
public List<Item> getMostProfitablePossibleSequence(int capacity) {
if (elements.size() == 1) {
return elements;
}
List<Item> itemsSortedByCost = new ArrayList<>(elements);
itemsSortedByCost.sort(Comparator.comparingInt(Item::getCost));
int limit = capacity / weight;
if (limit > itemsSortedByCost.size()) {
return itemsSortedByCost;
}
return itemsSortedByCost.subList(itemsSortedByCost.size() - limit, itemsSortedByCost.size());
}
}
private record ItemsCostInfo(
List<Item> items,
int cost
) {
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
ItemsCostInfo that = (ItemsCostInfo) o;
return cost == that.cost && Objects.equals(items, that.items);
}
@Override
public int hashCode() {
return Objects.hash(items, cost);
}
}
private static class ItemSelectionResult {
private final List<Branch> branches;
public ItemSelectionResult(Item rootItem) {
this.branches = new ArrayList<>();
this.branches.add(new Branch());
this.getLastBranch().addInBranch(rootItem);
}
public boolean isEmpty() {
return branches.isEmpty();
}
public Branch getLastBranch() {
return branches.getLast();
}
public ItemsCostInfo getBranchWithMaxCost() {
int maxCost = -1;
List<Item> branchElementsWithMaxCost = new ArrayList<>();
for (Branch branch : branches) {
int costOfBranch = branch.getCost();
if (maxCost < costOfBranch) {
maxCost = costOfBranch;
branchElementsWithMaxCost = branch.getItemsInOrder();
}
}
return new ItemsCostInfo(branchElementsWithMaxCost, maxCost);
}
public Branch createCapableBranchFromLast(Item newItem, int capacity) {
int newWeight = newItem.getWeight();
int weightOfLastElement = getLastBranch().getWeight();
Branch lastBranchCopy = getLastBranch().getCopy();
if (weightOfLastElement + newWeight <= capacity) {
lastBranchCopy.addInBranch(newItem);
return lastBranchCopy;
}
while (!lastBranchCopy.isEmpty() && weightOfLastElement + newWeight > capacity) {
lastBranchCopy.removeLast();
if (lastBranchCopy.isEmpty()) {
return lastBranchCopy;
}
weightOfLastElement = lastBranchCopy.getWeight();
}
lastBranchCopy.addInBranch(newItem);
return lastBranchCopy;
}
public void addInLastBranch(Item item) {
getLastBranch().addInBranch(item);
}
public void addNewBranch(Branch branch) {
branches.add(branch);
}
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
ItemSelectionResult that = (ItemSelectionResult) o;
return Objects.equals(branches, that.branches);
}
@Override
public int hashCode() {
return Objects.hashCode(branches);
}
}
private static class Branch {
private final List<Item> itemsInOrder;
private Integer cost;
private Integer weight;
public Branch() {
this.itemsInOrder = new ArrayList<>();
this.cost = 0;
this.weight = 0;
}
public Branch(List<Item> items) {
this.itemsInOrder = items;
this.cost = items.stream().map(Item::getCost).reduce(Integer::sum).orElse(0);
this.weight = items.stream().map(Item::getWeight).reduce(Integer::sum).orElse(0);
}
public Branch getCopy() {
return new Branch(new ArrayList<>(itemsInOrder));
}
public Integer getWeight() {
return weight;
}
public Integer getCost() {
return cost;
}
public List<Item> getItemsInOrder() {
return itemsInOrder;
}
public void removeLast() {
int weightOfLastElement = itemsInOrder.getLast().getWeight();
int costOfLastElement = itemsInOrder.getLast().getCost();
this.itemsInOrder.removeLast();
this.weight -= weightOfLastElement;
this.cost -= costOfLastElement;
}
public void addInBranch(Item item) {
this.itemsInOrder.add(item);
this.cost += item.getCost();
this.weight += item.getWeight();
}
public boolean isEmpty() {
return this.itemsInOrder.isEmpty();
}
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
Branch branch = (Branch) o;
return Objects.equals(itemsInOrder, branch.itemsInOrder) && Objects.equals(cost, branch.cost) && Objects.equals(weight, branch.weight);
}
@Override
public int hashCode() {
return Objects.hash(itemsInOrder, cost, weight);
}
}
}
Теперь комментирую.
Внутреннее состояние нашего рюкзака - itemsInBackpack (наиболее выгодное наполнение Item-ами, которое подбирается при каждом вызове fillBackpack) и capacity (вместимость рюкзака). Инициализация в конструкторе всего этого дела, думаю, в комментариях не нуждается.
Переходим к самому интересному - fillBackpack.
Наша задача, как и было оговорено, делится на два логических шага. Первое - выявить все возможные и как можно более длинные варианты наполнения. Второе - найти среди них то, что имеет наивысшую суммарную цену, и сложить это дело в itemsInBackpack.
Самым сложным является первый шаг. Как он осуществляется.
Принимаем поступившее множество предметов за S. Нам необходимо обработать это множество определенным образом и получить из него массив предметов M.
Исключаем из S элементы, вес которых больше вместимости рюкзака, чтобы не спотыкаться о мусор.
Группируем предметы из S по весу. Для этого хорошо подходит HashMap. В моем классе BackpackImpl это происходит в методе preProcessItems. Каждая группа предметов "по весу" соответствует экземпляру класса WeightSequenceInfo.
Извлекаем самые выгодные наборы предметов в рамках каждой отдельной группы G. Делается это следующим образом:
Если группа G состоит только из одного элемента - просто возвращаем эту группу.
Сортируем элементы группы G по цене.
Получаем результат деления вместимости рюкзака на вес группы G, округляя в меньшую сторону. Принимаем его за L.
Если L больше размера группы G - возвращаем G.
Если L не превышает размер группы G - возвращаем L элементов с конца группы G.
Все полученные наборы предметов объединяем в один массив M.
Сортируем элементы M по весу в порядке возрастания.
Возвращаем массив M, в дальнейшем подборе будет участвовать именно он.
Создаем массив R из результатов подбора наполнений, в котором каждый элемент будет соответствовать некоему элементу из M.
Берем i-тый элемент массива M. Наша задача - получить все варианты наполнения с ним, соотнося с другими элементами. Для этого:
Создаем такую сущность, как "ветка". Ветка и является неким возможным наполнением с i-тым элементом, которое должно укладываться в ограничение по весу.
Первая ветка должна просто содержать i-тый элемент.
Переходим на следующий элемент массива M, j. Получаем сумму по весу последней созданной ветки (на самой первой итерации это будет первая ветка с одиноким i-тым элементом) и j-того элемента. Сумма укладывается в ограничение? Ложим в конец последней созданной ветки j-тый элемент.
Сумма не укладывается в ограничение? Пытаемся сформировать новую ветку. Делается это за счет того, что из копии предыдущей ветки исключаются элементы (начиная с последнего добавленного) ровно до тех пор, пока сумма не начнет укладываться в ограничение. Когда она уложилась в ограничение - на базе копии ветки с удаленными "мешавшими" элементами создаем новую ветку, уже с добавленным в конец j-тым элементом.
Если получилось так, что в процессе подбора новой ветки мы удалили из копии все, включая, разумеется, i-тый элемент - то в принципе весь процесс подбора веток для i-того элемента можно сворачивать, т.к. с учетом изначальной сортировки M по весу дальше будет только хуже.
Повторяем процесс с 3-го пункта ровно до тех пор, пока не пройдем через все элементы массива M по j.
Запоминаем все ветки для i, как единый результат C.
Cмы начинаем соотносить с предыдущими результатами и чистить мусор.Берем веткуkизC.Берем предыдущий результатPиз массиваR.Если вPсодержится хотя бы одна ветка, которая включает все элементы веткиk- тоkдля нас уже бессмысленна. Запоминаем веткуk, как подлежащую удалению, переходим к следующей ветке текущего результата. Если жеPне содержит таких веток - идем к следующемуPдо тех пор, пока не пройдем весь массивR.Удаляем изCвсе, что подлежит удалению.
Ложим C в R.
Повторяем процесс до тех пор, пока не переберем все элементы в M по i.
Таким образом мы получаем те самые варианты наполнения.
В принципе, можно было бы обойтись без шага 5 - он у меня появился чуть позже, и без него все тесты все равно проходили. Но опять-таки, при возросшей сложности формирования возможных наполнений (прим. из будущего: при ЕЩЕ КАК возросшей, "гений"!) мы снижаем сложность последующего поиска максимума, да и от мусора просто избавляемся, укладываясь в изначальную формулировку плана про все возможные и как можно более длинные варианты наполнения.
upd: шаг 5 - это слишком дорогостоящая операция, сильно портящая быстродействие алгоритма. На данный момент я отказался от этого шага, но, возможно, удастся его как-нибудь оптимизировать. Из примеров кода я это убрал, как и из репозитория. Но всем, кому внезапно интересно, как оно выглядело - добро пожаловать в коммит test11 postprocessresult was a bad idea. Чтобы вы понимали: тест test11 с 1000 элементов вместе с этой пост-обработкой повисал на время больше минуты; без - решается за время в пределах 200-300 мс. Что уже не так уж и плохо, как по мне.
Под-алгоритм формирования массива M исключительно важен! Группировка по весу и последующая обработка появилась исходя из того, что элементы могут многократно повторяться по весу (спасибо юзеру iantonspb за указание на подобные кейсы), и без нее алгоритм будет спотыкаться в дальнейшем; исключительно важно отсортировать M по весу в порядке возрастания; в общем, про первый шаг ни в коем случае не забываем.
Всю описанную логику fillBackpack и проделывает до того, как приступит к выявлению максимума на полученных наполнениях. Комментировать сам код, думаю, особого смысла не имеет - он делает ровно то, что уже описано.
Теперь работа довольно скучная. Из каждого i-того результата с вариантами наполнений мы берем тот вариант, что имеет максимальную суммарную цену - и ищем максимум уже среди всех извлеченных таким образом вариантов. Эта часть
int maxCost = -1;
List<Item> branchWithMaxCost = new ArrayList<>();
for (ItemSelectionResult selectionResult : selectionResults) {
if (selectionResult.isEmpty()) {
continue;
}
ItemsCostInfo itemsCostInfo = selectionResult.getBranchWithMaxCost();
int currentCost = itemsCostInfo.cost();
if (currentCost > maxCost) {
maxCost = currentCost;
branchWithMaxCost = itemsCostInfo.items();
}
}и проделывает озвученную логику.
Довершаем картину тем, что branchWithMaxCost ложим в itemsInBackpack. На этом вроде как и все.
Стоит еще добавить: в целом мы можем находить не только первое попавшееся выгодное наполнение, а вообще все наиболее выгодные наполнения. Делается это элементарно: мы запоминаем, какой у нас конечный maxCost, потом в отдельном цикле собираем все getBranchWithMaxCost(), что равны этому maxCost. Добавлять слишком лень, класс слишком сильно заточил под один набор, и без того была уже куча изменений. Но стоит иметь в виду, это может быть очень полезно + справится и пятиклассник.
Заключение
Тест-кейсы, с которыми все отрабатывает, выглядят так.
Тест-кейсы
package com.smolka;
import com.smolka.backpack.Backpack;
import com.smolka.backpack.Item;
import com.smolka.backpack.impl.BackpackImpl;
import org.junit.Test;
import java.util.HashSet;
import java.util.Set;
public class BackpackTest {
@Test
public void test11() {
Set<Item> items = new HashSet<>();
for (int i = 1; i < 1000; i++) {
items.add(new Item(String.valueOf(i), i, i));
}
int check = 1999;
Backpack backpack = new BackpackImpl(1999);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test10() {
Set<Item> items = Set.of(
new Item("1", 1, 1),
new Item("2", 1, 2),
new Item("3", 1, 3),
new Item("4", 2, 10)
);
int check = 13;
Backpack backpack = new BackpackImpl(3);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test9() {
Set<Item> items = Set.of(
new Item("1", 1, 1),
new Item("2", 1, 2),
new Item("3", 1, 3),
new Item("4", 1, 4),
new Item("5", 2, 5),
new Item("6", 2, 6),
new Item("7", 3, 7),
new Item("8", 3, 8)
);
int check = 15;
Backpack backpack = new BackpackImpl(5);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test8() {
Set<Item> items = Set.of(
new Item("1", 1, 1),
new Item("2", 1, 2),
new Item("3", 1, 3),
new Item("4", 1, 4),
new Item("5", 1, 5),
new Item("6", 1, 6),
new Item("8", 1, 8),
new Item("9", 1, 9),
new Item("21", 1, 21),
new Item("10", 1, 10),
new Item("11", 1, 11),
new Item("12", 1, 12),
new Item("13", 1, 13),
new Item("14", 1, 14),
new Item("15", 1, 15),
new Item("16", 1, 16),
new Item("17", 1, 17),
new Item("52", 2, 1000),
new Item("19", 1, 19),
new Item("20", 1, 20),
new Item("22", 1, 22),
new Item("23", 1, 23),
new Item("24", 1, 24),
new Item("25", 1, 25),
new Item("26", 1, 26),
new Item("51", 2, 1000),
new Item("27", 1, 27),
new Item("28", 1, 28),
new Item("29", 1, 29),
new Item("30", 1, 30),
new Item("31", 1, 31),
new Item("32", 1, 32),
new Item("33", 1, 33),
new Item("34", 1, 34),
new Item("35", 1, 35),
new Item("36", 1, 36),
new Item("18", 1, 18),
new Item("37", 1, 37),
new Item("38", 1, 38),
new Item("39", 1, 39),
new Item("40", 1, 40),
new Item("41", 1, 41),
new Item("42", 1, 42),
new Item("7", 1, 7),
new Item("43", 1, 43),
new Item("44", 1, 44),
new Item("45", 1, 45),
new Item("46", 1, 46),
new Item("47", 1, 47),
new Item("48", 1, 48),
new Item("49", 1, 49),
new Item("50", 1, 50)
);
int check = 2285;
Backpack backpack = new BackpackImpl(10);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test1() {
Set<Item> items = Set.of(
new Item("Часы", 1, 4),
new Item("Пакет сока", 2, 3),
new Item("Банка помидоров", 7, 2),
new Item("Ржавый портсигар", 3, 1),
new Item("Планшет", 8, 6)
);
int check = 10;
Backpack backpack = new BackpackImpl(9);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test2() {
Set<Item> items = Set.of(
new Item("Консервы", 5, 3),
new Item("Гиря", 10, 5),
new Item("Банка гвоздей", 6, 4),
new Item("Кулон", 5, 2)
);
int check = 7;
Backpack backpack = new BackpackImpl(14);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test3() {
Set<Item> items = Set.of(
new Item("Коробок кубинских сигар", 15, 60),
new Item("Платиновое ожерелье", 30, 90),
new Item("Золотой слиток", 50, 100)
);
int check = 190;
Backpack backpack = new BackpackImpl(80);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test4() {
Set<Item> items = Set.of(
new Item("Брат", 10, 100),
new Item("Сестра", 20, 80),
new Item("Первая научная история войны 1812 года, 3 издание", 50, 1000)
);
int check = 1000;
Backpack backpack = new BackpackImpl(50);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test5() {
Set<Item> items = Set.of(
new Item("Статуэтка", 4, 1),
new Item("Столовые принадлежности", 5, 2),
new Item("Пачка сигарет", 1, 3)
);
int check = 3;
Backpack backpack = new BackpackImpl(4);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test6() {
Set<Item> items = Set.of(
new Item("Бокс 1", 4, 2),
new Item("Бокс 2", 4, 2),
new Item("Бокс 3", 4, 2)
);
int check = 4;
Backpack backpack = new BackpackImpl(8);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
@Test
public void test7() {
Set<Item> items = Set.of(
new Item("Бокс 1", 4, 2),
new Item("Бокс 2", 4, 2),
new Item("Бокс 3", 4, 2)
);
int check = 0;
Backpack backpack = new BackpackImpl(3);
backpack.fillBackpack(items);
assert backpack.getCostOfContent() == check;
assert backpack.getWeightOfContent() <= backpack.getCapacity();
}
}
Среди них есть, например, test3. Если верить вики, то на этом кейсе не отрабатывает тот же жадный алгоритм, но мой вроде бы справляется.
К оценке сложности пока не приступал, но на поверхностный взгляд сложность не такая уж и высокая.
Если это действительно так - то тогда я пока отказываюсь верить, что алгоритм рабочий на 100%. Как-то все слишком просто. В любом случае буду рад, если кто-нибудь сведущий накинет каких-нибудь более интересных и хитрых кейсов.
Пока что как-то так. Делитесь впечатлениями, критикуйте и так далее)
Всем добра и всем дзякую!
