【华为面试题】动态规划

Love The Way You Lie 2024-03-23 22:18 12阅读 0赞

### 题目 ###

题目描述：  
一个充电站有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

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关【华为面试题】动态规划

题目题目描述：一个充电站有n个不同功率的充电设备。您的任务是从中选取若干个设备，使得他们的总功率最接近但不超过充电站的最大输出功率P\_max。输入：第一

Love The Way You Lie/ 2024年03月23日 22:18/ 0 赞/ 13 阅读

相关 JAVA-高频面试题汇总:动态规划

前言为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳。目录: [JAVA-高频面试题汇总:动态规划][JAVA-] [JAVA

小咪咪/ 2023年01月01日 03:36/ 0 赞/ 143 阅读

相关动态规划题 leetcode

1. [62. 不同路径][62.] 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人

我不是女神ヾ/ 2022年12月27日 08:51/ 0 赞/ 180 阅读

相关动态规划：基本概念以及面试常见题型

动态规划入门动态规划基本概念数字三角形动规四要素动态规划的使用场景与题型分类

淩亂°似流年/ 2022年11月09日 01:27/ 0 赞/ 168 阅读

相关面试经典动态规划问题

经典动态规划问题三角数塔问题设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： ![图1][1] 要求从根

落日映苍穹つ/ 2022年07月12日 10:51/ 0 赞/ 181 阅读

相关面试经典动态规划问题

经典动态规划问题三角数塔问题设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： ![图1][1] 要求从根

曾经终败给现在/ 2022年07月12日 10:51/ 0 赞/ 216 阅读

相关杭电动态规划题

Monkey and Banana Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/3

喜欢ヅ旅行/ 2022年06月14日 00:50/ 0 赞/ 150 阅读

相关动态规划的两个经典例子（面试题）

1、动态规划动态规划问题是面试题中的热门话题，如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，

待我称王封你为后i/ 2022年05月17日 09:35/ 0 赞/ 161 阅读

相关 leetcode 动态规划类型题

1，Triangle ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 int mininumTotal

怼烎@/ 2021年12月03日 08:10/ 0 赞/ 237 阅读

相关谷歌面试题——动态规划

> \谷歌面试题\ 两个鸡蛋：两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋以最少的次数确定哪一层是鸡

野性酷女/ 2021年11月15日 12:28/ 0 赞/ 282 阅读