'use strict';

class Item {
    /**
     * @param {number} weight
     * @param {number} value
     * @param {?string=} [label]
     */
    constructor(weight, value, label) {
        this.weight = weight;
        this.value = value;
        this.label = label;
    }

    /**
     * @returns {number}
     */
    get valuePerWeight() {
        return this.value / this.weight;
    }
};

class Node {
    /**
     * @param {[Item]} items
     * @param {number} weightAvail
     * @param {number} valueBase
     */
    constructor(items, weightAvail, valueBase) {
        this.items = items;
        this.valueBase = valueBase;
        this.weightTotal = weightAvail;
        this.counts = new Array(items.length).fill(0);

        let upperBound = valueBase, lowerBound = valueBase, branchIdx = -1;

        for (let i = 0; i < items.length; ++i) {
            const currentWeight = items[i].weight;
            if (weightAvail < currentWeight) {
                this.counts[i] = weightAvail / currentWeight;
                upperBound = lowerBound + this.counts[i] * items[i].value;
                branchIdx = i;
                break;
            }
            this.counts[i] = 1;
            weightAvail -= currentWeight;

            lowerBound += items[i].value;
        }

        this.lowerBound = lowerBound;
        this.upperBound = upperBound < lowerBound ? lowerBound : upperBound;
        this.branchIdx = branchIdx;
    }
};

/**
 * @param {Node} node
 */
const bounds = function(node) {
    return [node.lowerBound, node.upperBound];
};

/**
 * @param {Node} node
 */
const branch = function(node) {
    const itemsLeft = node.items.slice(0); // clone
    itemsLeft.splice(node.branchIdx, 1);

    if (itemsLeft.length !== 0) {
        let result = [
            new Node(itemsLeft, node.weightTotal, node.valueBase),
            new Node(itemsLeft, node.weightTotal - node.items[node.branchIdx].weight, node.valueBase + node.items[node.branchIdx].value),
        ];
        return result;
    }

    return [];
};

class BnB {
    /**
     * @param {function(TNode) : [TNode]} branch
     * @param {function(TNode) : [number]} bounds
     * @template TNode
     */
    constructor(branch, bounds) {
        this.branch = branch;
        this.bounds = bounds;
    }

    /**
     * @param {TNode} rootNode
     */
    solve(rootNode) {
        let [lowerBound, upperBound] = this.bounds(rootNode);
        let bestLowerBound = lowerBound,
            bestUpperBound = upperBound;
        let bestNode = rootNode;

        let queue = [rootNode];
        while (queue.length > 0) {
            const currentNode = queue.pop();
            const childNodes = this.branch(currentNode);
            console.log(JSON.stringify(childNodes));
            for (let i = 0; i < childNodes.length; ++i) {
                const childNode = childNodes[i];
                const [lowerBound, upperBound] = this.bounds(childNode);
                if (lowerBound >= bestLowerBound) {
                    bestLowerBound = lowerBound;
                    bestNode = childNode;
                }
                /// todo: check condition (< or <=)
                if (upperBound < bestLowerBound) {
                    // skip
                    continue;
                }
                if (lowerBound >= upperBound) {
                    break;
                }

                queue.push(childNode);
            }
        }

        return bestNode;
    }
};

// const items = [
//     new Item(25, 200),
//     new Item(30, 300),
//     new Item(50, 250),
//     new Item(10, 320),
//     new Item(60, 180),
// ]
const items = [
    new Item(9, 150),
    new Item(13, 35),
    new Item(153, 200),
    new Item(50, 160),
    new Item(15, 60),
    new Item(68, 45),
    new Item(27, 60),
    new Item(39, 40),
    new Item(23, 30),
    new Item(52, 10),
    new Item(11, 70),
    new Item(32, 30),
    new Item(24, 15),
    new Item(48, 10),
    new Item(73, 40),
    new Item(42, 70),
    new Item(43, 75),
    new Item(22, 80),
    new Item(7, 20),
    new Item(18, 12),
    new Item(4, 50),
    new Item(30, 10),
]
.sort((a, b) => b.valuePerWeight - a.valuePerWeight);

const rootNode = new Node(items, 400, 0);
const bnb = new BnB(branch, bounds);

const resultNode = bnb.solve(rootNode);
console.log(JSON.stringify(resultNode));