编辑代码

class Item {
    constructor(name, value, weight) {
        this.name = name
        this.weight = weight;
        this.value = value;
    }
}

function knapsackBranchAndBound(items, capacity) {
    // 根据物品价值密度（价值/重量）进行排序
    items.sort((a, b) => b.value / b.weight - a.value / a.weight);

    let maxValue = 0;
    let bestCombination = [];

    function branchAndBound(index, currentWeight, currentValue, included) {
        // 如果当前价值加上剩余物品的价值小于最大价值，则不再继续搜索
        if (currentValue > maxValue) {
            maxValue = currentValue;
            bestCombination = [...included];
        }

        if (index < items.length) { //结束条件
            branchAndBound(index + 1, currentWeight, currentValue, [...included]);

            // 如果当前物品可以放入背包，则继续搜索
            if (currentWeight + items[index].weight <= capacity) {
                branchAndBound(index + 1, currentWeight + items[index].weight, currentValue + items[index].value, [...included, items[index]]);
            }
        }
    }

    branchAndBound(0, 0, 0, []);

    return {
        maxValue,
        bestCombination
    };
}

// 示例
const items = [
    new Item("IPhone", 2000, 1),
    new Item("吉他", 1500, 1),
    new Item("笔记本电脑", 2000, 3),
    new Item("音箱", 3000, 4)
];

const capacity = 8;

const result = knapsackBranchAndBound(items, capacity);
console.log("最大价值", result.maxValue);
console.log("最佳组合", result.bestCombination);