• новости
• статьи
• блоги
• файлы
• пресс-релизы

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.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.UUID;
import java.util.stream.Collectors;

public class BackpackImpl implements Backpack {

    private final Set itemsInBackpack;

    private final int capacity;

    public BackpackImpl(int capacity) {
        assert capacity > 0;

        this.itemsInBackpack = new HashSet<>();
        this.capacity = capacity;
    }

    @Override
    public void fillBackpack(Set items) {
        itemsInBackpack.clear();

        Set itemsWithoutOverWeightedElements = items.stream().filter(item -> item.getWeight() <= capacity).collect(Collectors.toSet());

        List sortedItems = new ArrayList<>(itemsWithoutOverWeightedElements.stream().toList());
        sortedItems.sort(Comparator.comparingInt(Item::getWeight));

        List selectionResults = new ArrayList<>();
        for (int i = 0; i < sortedItems.size(); i++) {
            addSelectionResultForIndex(i, sortedItems, selectionResults);
        }

        int maxCost = -1;
        List 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 getItemsInBackpack() {
        return itemsInBackpack;
    }

    @Override
    public int getCapacity() {
        return capacity;
    }

    private void addSelectionResultForIndex(int index, List items, List 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.getWeightOfLastBranch() + nextItem.getWeight();
            if (newWeight > capacity) {
                Branch newBranch = result.createCapableBranchFromLast(nextItem, capacity);
                if (newBranch.isEmpty()) {
                    otherResults.add(postProcessResultAndReturn(result, otherResults));
                    return;
                }

                result.addNewBranch(newBranch);
            } else {
                result.addInLastBranch(nextItem);
            }
        }

        otherResults.add(postProcessResultAndReturn(result, otherResults));
    }

    private ItemSelectionResult postProcessResultAndReturn(ItemSelectionResult result, List otherResults) {
        Set branchesToRemove = new HashSet<>();
        for (Branch branch : result.getBranches()) {
            for (ItemSelectionResult otherResult : otherResults) {
                if (otherResult.containsAsSubCombination(branch.getItemsCombination())) {
                    branchesToRemove.add(branch.getUuid());
                    break;
                }
            }
        }

        result.removeAllBranchesByUuids(branchesToRemove);
        return result;
    }

    private record ItemsCostInfo(
            List 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 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 List getBranches() {
            return branches;
        }

        public boolean containsAsSubCombination(Set items) {
            for (Branch branch : branches) {
                if (branch.combinationContainsAll(items)) {
                    return true;
                }
            }

            return false;
        }

        public void removeAllBranchesByUuids(Set toRemove) {
            branches.removeIf(b -> toRemove.contains(b.getUuid()));
        }

        public ItemsCostInfo getBranchWithMaxCost() {
            int maxCost = -1;
            List branchElementsWithMaxCost = new ArrayList<>();

            for (Branch branch : branches) {
                List branchElements = branch.getItemsInOrder();
                int costOfBranch = getCostOfBranchElements(branchElements);
                if (maxCost < costOfBranch) {
                    maxCost = costOfBranch;
                    branchElementsWithMaxCost = branchElements;
                }
            }

            return new ItemsCostInfo(branchElementsWithMaxCost, maxCost);
        }

        public Branch createCapableBranchFromLast(Item newItem, int capacity) {
            int newWeight = newItem.getWeight();
            List lastBranchElementsCopy = new ArrayList<>(getLastBranch().getItemsInOrder());
            if (getWeightOfLastBranch() + newWeight <= capacity) {
                lastBranchElementsCopy.add(newItem);
                return new Branch(lastBranchElementsCopy);
            }

            while (!lastBranchElementsCopy.isEmpty() && getWeightOfBranchElements(lastBranchElementsCopy) + newWeight > capacity) {
                lastBranchElementsCopy.removeLast();
                if (lastBranchElementsCopy.isEmpty()) {
                    return new Branch(lastBranchElementsCopy);
                }
            }

            lastBranchElementsCopy.add(newItem);

            return new Branch(lastBranchElementsCopy);
        }

        public int getWeightOfLastBranch() {
            return getWeightOfBranchElements(getLastBranch().getItemsInOrder());
        }

        public void addInLastBranch(Item item) {
            getLastBranch().addInBranch(item);
        }

        public void addNewBranch(Branch branch) {
            branches.add(branch);
        }

        private int getWeightOfBranchElements(List branch) {
            return branch.stream().map(Item::getWeight).reduce(Integer::sum).orElse(0);
        }

        private int getCostOfBranchElements(List branch) {
            return branch.stream().map(Item::getCost).reduce(Integer::sum).orElse(0);
        }

        @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 UUID uuid;

        private final List itemsInOrder;

        private final Set itemsCombination;

        public Branch() {
            this.uuid = UUID.randomUUID();
            this.itemsInOrder = new ArrayList<>();
            this.itemsCombination = new HashSet<>();
        }

        public Branch(List items) {
            this.uuid = UUID.randomUUID();
            this.itemsInOrder = items;
            this.itemsCombination = new HashSet<>(items);
        }

        public UUID getUuid() {
            return uuid;
        }

        public List getItemsInOrder() {
            return itemsInOrder;
        }

        public Set getItemsCombination() {
            return itemsCombination;
        }

        public boolean combinationContainsAll(Set otherItems) {
            return itemsCombination.containsAll(otherItems);
        }

        public void addInBranch(Item item) {
            this.itemsInOrder.add(item);
            this.itemsCombination.add(item);
        }

        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(uuid, branch.uuid);
        }

        @Override
        public int hashCode() {
            return Objects.hashCode(uuid);
        }
    }
}

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.Set;

public class BackpackTest {

    @Test
    public void test() {
        Set 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 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 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 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 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 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 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();
    }
}