编辑代码

function knapsack(items, capacity) {
    const n = items.length;
    const dp = new Array(n + 1).fill(null).map(() => new Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (items[i - 1].weight <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i - 1].weight] + items[i - 1].value);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    let selectedItems = [];
    let remainingCapacity = capacity;
    for (let i = n; i > 0 && remainingCapacity > 0; i--) {
        if (dp[i][remainingCapacity] !== dp[i - 1][remainingCapacity]) {
            selectedItems.push(items[i - 1]);
            remainingCapacity -= items[i - 1].weight;
        }
    }

    return {
        selectedItems: selectedItems.reverse(),
        totalValue: dp[n][capacity]
    };
}

const fruits = [
    { name: '苹果', weight: 15, value: 300 },
    { name: '香蕉', weight: 18, value: 180 },
    { name: '橘子', weight: 10, value: 150 },
    { name: '猕猴桃', weight: 9, value: 270 }
];

const capacity = 20;

const result = knapsack(fruits, capacity);
console.log("装水果的策略：", result.selectedItems.map(item => item.name).join(', '));
console.log("总价值：", result.totalValue);