题目
题目描述:
一个充电站有n个不同功率的充电设备。您的任务是从中选取若干个设备,使得他们的总功率最接近但不超过充电站的最大输出功率P_max。
输入:
第一行:一个整数n,代表充电设备的数量。
第二行:n个整数,分别代表每个设备的功率。
第三行:一个整数,代表充电站的最大输出功率P_max。
输出:
一个整数,代表选取的设备的总功率,该总功率应最接近但不超过P_max。
示例:
输入:
4
50 20 20 60
90
输出:
90
解释:
选取功率为50、20、20的设备,总功率为90,最接近但不超过充电站的最大输出功率。
代码
function getMaxPower(n, p, p_max) {
// 初始化动态规划的二维数组,大小为 (n+1) x (p_max+1),所有元素初值为0
let dp = Array(n + 1)
.fill()
.map(() => Array(p_max + 1).fill(0));
// 初始化第0行,考虑使用第一个设备时的情况
for (let j = p_max; j >= p[0]; j--) {
dp[0][j] = dp[0][j - p[0]] + p[0];
}
// 对于每一个设备(从第二个到最后一个)
for (let i = 1; i < n; i++) {
// 对于每一个可能的总功率值
for (let j = 0; j <= p_max; j++) {
// 如果当前的功率j小于设备的功率,那么就不能加入这个设备
if (j < p[i]) {
dp[i][j] = dp[i - 1][j];
} else {
// 否则,考虑两种情况:加入当前设备或不加入。取两者的最大值。
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] + p[i]);
}
}
}
// 返回dp数组的最后一行的最后一个元素,它表示使用所有设备并且总功率不超过p_max的最大总功率。
return dp[n - 1][p_max];
}
// 示例1
let n1 = 4;
let p1 = [50, 20, 20, 60];
let p_max1 = 90;
console.log(getMaxPower(n1, p1, p_max1)); // 输出: 90
// 示例2
let n2 = 2;
let p2 = [50, 40];
let p_max2 = 30;
console.log(getMaxPower(n2, p2, p_max2)); //输出: 0