function maximizeValue() {
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 n = fruits.length;
// 初始化dp表格
const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= capacity; j++) {
if (fruits[i - 1].weight > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - fruits[i - 1].weight] + fruits[i - 1].value);
}
}
}
// 回溯找出装入水果的策略
let i = n;
let j = capacity;
const selectedFruits = [];
while (i > 0 && j > 0) {
if (dp[i][j] !== dp[i - 1][j]) {
selectedFruits.push(fruits[i - 1]);
j -= fruits[i - 1].weight;
}
i--;
}
return selectedFruits;
}
const selectedFruits = maximizeValue();
console.log('装水果的策略为:', selectedFruits);