2025-11-13：折扣价交易股票的最大利润。用go语言，公司有 n 名员工，编号从 1 到 n，编号 1 为 CEO。 pr

2025-11-13：折扣价交易股票的最大利润。用go语言，公司有 n 名员工，编号从 1 到 n，编号 1 为 CEO。

present[i] 是第 i 位员工今天买入该员工股票所需的价格；future[i] 是明天卖出该员工股票能得到的期望价格（两个数组长度均为 n，索引从 1 开始）。

hierarchy 给出直接汇报关系：每个元素为一对 [u, v]，表示 u 是 v 的直接上司。

预算 budget 是可用于买入股票的初始资金（只能用这笔钱付款，不能先买后卖再用收益继续买）。

折扣规则：如果某位员工的直接上司也购买了自己的股票，那么该下属在今天买入时价格变为 floor(present[v] / 2)。

每只股票最多买一次。购买后可在明天以对应的 future 价格卖出，单只股票的净收益为 future[i]
减去实际支付的买入价（若为负则可选择不买）。

目标：在不超过初始预算的前提下，选择一组买入决策（同时决定哪些上司也买以触发折扣），使得所有选中股票在明天卖出后获得的总利润最大，并返回该最大利润值。

1 <= n <= 160。

present.length, future.length == n。

1 <= present[i], future[i] <= 50。

hierarchy.length == n - 1。

hierarchy[i] == [ui, vi]。

1 <= ui, vi <= n。

ui != vi。

1 <= budget <= 160。

没有重复的边。

员工 1 是所有员工的直接或间接上司。

输入的图 hierarchy 保证 无环 。

输入： n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10。

输出： 10。

解释：

员工 1 以价格 4 购买股票，获得利润 7 - 4 = 3。

员工 3 可获得折扣价 floor(8 / 2) = 4，获得利润 11 - 4 = 7。

员工 1 和员工 3 的总购买成本为 4 + 4 = 8 <= budget，因此最大总利润为 3 + 7 = 10。

题目来自力扣3562。

过程描述

1. 1.构建员工树结构：

• • 根据输入的hierarchy（直接汇报关系），构建一个树形结构的邻接表g。每个节点代表一名员工，编号从0开始（对应原始编号1到n），其中节点0是CEO（根节点）。每个节点x的邻接表g[x]存储其所有直接下属（子节点）的编号。由于输入保证无环且员工1是所有员工的直接或间接上司，因此构建的树是以0为根的有根树。

2.递归DFS遍历与状态定义：

• • 定义一个递归函数dfs(x)，用于处理以节点x为根的子树。该函数返回一个包含两个数组的结构[2][]int，每个数组长度为budget + 1：

• • • 第一个数组（索引0）表示当x的直接上司不购买股票时，以x为根的子树在不同预算（0到budget）下能获得的最大利润。

  • • 第二个数组（索引1）表示当x的直接上司购买股票时，对应子树在不同预算下的最大利润。

• • 初始时，所有利润值被设置为一个极小的负数（math.MinInt / 2），表示不可行状态，但预算为0时利润为0。

3.合并子节点利润（子树合并）：

• • 对于当前节点x，遍历其每个直接下属（子节点）y：

• • • 递归调用dfs(y)，获取子节点y的利润数组fy。fy[0]和fy[1]分别对应y的上司（即x）不买或买股票时y子树的利润。

  • • 将每个子节点y的利润合并到x的临时状态数组subF中。合并过程类似分组背包问题：

  • • • 对于每个可能的预算j（从0到budget），以及分配给子节点y的预算jy（从0到j），计算将jy预算用于y子树所能获得的利润。如果fy[k][jy]为负（表示亏损），则跳过以优化效率。

    • • 通过动态规划更新subF[k][j]（其中k表示x的上司状态），取subF[k][j - jy] + fy[k][jy]的最大值，即分配jy预算给y子树后，剩余预算用于其他子树的利润之和。

4.处理当前节点x的购买决策：

• • 合并所有子节点利润后，得到subF数组，表示x的子树（不包括x本身）的利润。接下来计算x自身的购买决策：

• • •情况1：不购买x的股票：

  • • • 利润直接继承自subF[0]（因为x不买，其下属无法获得折扣，故使用subF[0]，对应下属的上司不买状态）。

  • •情况2：购买x的股票：

  • • • 实际成本cost取决于x的直接上司是否购买（即折扣规则）：

    • • • 如果上司购买（k = 1），成本为floor(present[x] / 2)（即present[x] / 2的整数除）。

      • • 如果上司不购买（k = 0），成本为全价present[x]。

    • • 利润计算公式为future[x] - cost（卖出价减成本），并加上subF[1]的利润（因为x购买后，其下属可享受折扣，故使用subF[1]，对应下属的上司购买状态）。

    • • 对于每个预算j（从cost到budget），更新利润：f[k][j] = max(f[k][j], subF[1][j - cost] + (future[x] - cost))。

5.根节点处理与结果提取：

• • 从根节点（员工0，即CEO）开始递归调用dfs(0)。由于根节点没有上司，其状态视为上司不购买（即使用k = 0）。

• • 最终，返回dfs(0)[0]数组中的最大值，即在预算范围内能获得的最大总利润。

• •时间复杂度：算法对每个节点处理一次。对于每个节点x，需要合并其所有子节点的利润，合并过程中需要遍历预算j（0到budget）和子节点预算jy（0到j），因此每个节点的处理时间为O(m × budget²)，其中m是x的子节点数量。由于每个节点仅被处理一次，总时间复杂度为O(n × budget²)。其中n ≤ 160，budget ≤ 160，因此最坏情况下约为160³ = 4,096,000次操作，在合理范围内。

• •额外空间复杂度：主要空间用于存储树结构邻接表（O(n)）和递归DFS的栈空间（O(n)）。此外，每个节点需要两个大小为budget + 1的数组存储状态，因此总空间复杂度为O(n × budget)。代入n和budget的上限，约为O(160 × 160) = O(25,600)。

此方法通过树形DP和背包合并高效地解决了带有折扣规则的股票利润最大化问题，确保在预算约束下找到最优解。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "slices"
)

 func maxProfit(n int, present []int, future []int, hierarchy [][]int, budget int) int {
    g := make([][]int, n)
    for _, e := range hierarchy {
        x, y := e[0]-1, e[1]-1
        g[x] = append(g[x], y)
    }

     var dfs func(int) [2][]int
    dfs = func(x int) [2][]int {
        // 计算从 x 的所有儿子子树 y 中，能得到的最大利润之和
        subF := [2][]int{make([]int, budget+1), make([]int, budget+1)}
        for i := 1; i <= budget; i++ {
            subF[0][i] = math.MinInt / 2 // 表示不存在对应的花费总和
            subF[1][i] = math.MinInt / 2
        }
        for _, y := range g[x] {
            fy := dfs(y)
            for k, fyk := range fy {
                nf := make([]int, budget+1)
                for i := 1; i <= budget; i++ {
                    nf[i] = math.MinInt / 2
                }
                for jy, resY := range fyk {
                    if resY < 0 { // 重要优化：物品价值为负数，一定不选
                        continue
                    }
                    for j := jy; j <= budget; j++ {
                        nf[j] = max(nf[j], subF[k][j-jy]+resY)
                    }
                }
                subF[k] = nf
            }
        }

         f := [2][]int{}
        for k := range 2 {
            // 不买 x，转移来源为 subF[0]，因为对于子树来说，父节点一定不买
            f[k] = slices.Clone(subF[0])
            cost := present[x] / (k + 1)
            // 买 x，转移来源为 subF[1]，因为对于子树来说，父节点一定买
            for j := cost; j <= budget; j++ {
                f[k][j] = max(f[k][j], subF[1][j-cost]+future[x]-cost)
            }
        }
        return f
    }

     return slices.Max(dfs(0)[0])
}

 func main() {
    n := 3
    present := []int{4, 6, 8}
    future := []int{7, 9, 11}
    hierarchy := [][]int{{1, 2}, {1, 3}}
    budget := 10
    result := maxProfit(n, present, future, hierarchy, budget)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import math
from typing import List

 def maxProfit(n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
    # 构建邻接表表示的树结构
    g = [[] for _ in range(n)]
    for e in hierarchy:
        x, y = e[0] - 1, e[1] - 1
        g[x].append(y)
    def dfs(x: int) -> List[List[int]]:
        # subF[0] 和 subF[1] 分别表示不买和买当前节点时的状态
        subF = [[-10**9] * (budget + 1) for _ in range(2)]
        # 初始化：预算为0时利润为0
        for i in range(2):
            subF[i][0] = 0
        # 遍历所有子节点
        for y in g[x]:
            fy = dfs(y)
            # 对每个状态（0: 不买, 1: 买）
            for k in range(2):
                nf = [-10**9] * (budget + 1)
                nf[0] = 0
                # 遍历子节点的所有可能预算分配
                for jy in range(budget + 1):
                    resY = fy[k][jy]
                    if resY < 0:  # 重要优化：利润为负，一定不选
                        continue
                    # 更新当前预算下的最大利润
                    for j in range(jy, budget + 1):
                        if subF[k][j - jy] >= 0:
                            nf[j] = max(nf[j], subF[k][j - jy] + resY)
                subF[k] = nf
        # 计算当前节点的最终状态
        f = [[-10**9] * (budget + 1) for _ in range(2)]
        for k in range(2):
            # 不买当前节点：从子节点状态0转移
            f[k] = subF[0][:]
            # 买当前节点：从子节点状态1转移
            cost = present[x] // (k + 1)
            for j in range(cost, budget + 1):
                if subF[1][j - cost] >= 0:
                    profit = future[x] - cost
                    f[k][j] = max(f[k][j], subF[1][j - cost] + profit)
        return f
    result = dfs(0)
    return max(result[0])

 def main():
    n = 3
    present = [4, 6, 8]
    future = [7, 9, 11]
    hierarchy = [[1, 2], [1, 3]]
    budget = 10
    result = maxProfit(n, present, future, hierarchy, budget)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

   


 using namespace std;

 const int NEG_INF = numeric_limits::min() / 2; // 相当于 math.MinInt / 2

 int n_global, budget_global;
vector present_global, future_global;
vector 
 
 int 
 >> g_global; 
 
 
 
 
 // DFS 返回两个 dp 数组： 
 
 
 // first = 父节点不买的情况下本节点子树的最优值 
 
 
 // second = 父节点买的情况下本节点子树的最优值 
 
 
 pair 
 
 int 
 >, vector< 
 int 
 >> dfs( 
 int 
  x) { 
 
 
      
 // 初始化 subF[0] 和 subF[1] 
 
 
     vector< 
 int 
 > subF0(budget_global +  
 1 
 , NEG_INF); 
 
 
     vector< 
 int 
 > subF1(budget_global +  
 1 
 , NEG_INF); 
 
 
     subF0[ 
 0 
 ] =  
 0 
 ; 
 
 
     subF1[ 
 0 
 ] =  
 0 
 ; 
 
 
 
 
      
 // 遍历所有孩子 
 
 
      
 for 
  ( 
 int 
  y : g_global[x]) { 
 
 
         auto fy = dfs(y); 
 
 
          
 for 
  ( 
 int 
  k =  
 0 
 ; k <=  
 1 
 ; k++) { 
 
 
             vector< 
 int 
 > nf(budget_global +  
 1 
 , NEG_INF); 
 
 
              
 const 
  vector< 
 int 
 >& fyk = (k ==  
 0 
  ? fy.first : fy.second); 
 
 
              
 for 
  ( 
 int 
  jy =  
 0 
 ; jy <= budget_global; jy++) { 
 
 
                  
 int 
  resY = fyk[jy]; 
 
 
                  
 if 
  (resY <  
 0 
 )  
 continue 
 ;  
 // 负值不选 
 
 
                  
 for 
  ( 
 int 
  j = jy; j <= budget_global; j++) { 
 
 
                      
 if 
  (k ==  
 0 
 ) { 
 
 
                         nf[j] = max(nf[j], subF0[j - jy] + resY); 
 
 
                     }  
 else 
  { 
 
 
                         nf[j] = max(nf[j], subF1[j - jy] + resY); 
 
 
                     } 
 
 
                 } 
 
 
             } 
 
 
              
 if 
  (k ==  
 0 
 ) subF0 = nf; 
 
 
              
 else 
  subF1 = nf; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // f[0] 和 f[1] 分别对应 dfs 返回的两个向量 
 
 
     vector< 
 int 
 > f0 = subF0; 
 
 
     vector< 
 int 
 > f1 = subF0;  
 // 克隆 subF0 
 
 
 
 
      
 for 
  ( 
 int 
  k =  
 0 
 ; k <=  
 1 
 ; k++) { 
 
 
          
 int 
  cost = present_global[x] / (k +  
 1 
 ); 
 
 
          
 for 
  ( 
 int 
  j = cost; j <= budget_global; j++) { 
 
 
              
 if 
  (subF1[j - cost] > NEG_INF /  
 2 
 ) {  
 // 有效状态 
 
 
                  
 int 
  profit = future_global[x] - cost; 
 
 
                  
 if 
  (k ==  
 0 
 ) { 
 
 
                     f0[j] = max(f0[j], subF1[j - cost] + profit); 
 
 
                 }  
 else 
  { 
 
 
                     f1[j] = max(f1[j], subF1[j - cost] + profit); 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  {f0, f1}; 
 
 
 } 
 
 
 
 
 int 
  maxProfit( 
 int 
  n,  
 const 
  vector< 
 int 
 >& present,  
 const 
  vector< 
 int 
 >& future, 
 
 
                
 const 
  vector 
 
 int 
 , 
 int 
 >>& hierarchy,  
 int 
  budget) { 
 
 
     g_global.assign(n, {}); 
 
 
      
 for 
  (auto &e : hierarchy) { 
 
 
          
 int 
  x = e.first -  
 1 
 ; 
 
 
          
 int 
  y = e.second -  
 1 
 ; 
 
 
         g_global[x].push_back(y); 
 
 
     } 
 
 
     n_global = n; 
 
 
     budget_global = budget; 
 
 
     present_global = present; 
 
 
     future_global = future; 
 
 
 
 
     auto f = dfs( 
 0 
 ); 
 
 
      
 return 
  *max_element(f.first.begin(), f.first.end()); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 3 
 ; 
 
 
     vector< 
 int 
 > present = { 
 4 
 ,  
 6 
 ,  
 8 
 }; 
 
 
     vector< 
 int 
 > future = { 
 7 
 ,  
 9 
 ,  
 11 
 }; 
 
 
     vector 
 
 int 
 , 
 int 
 >> hierarchy = {{ 
 1 
 ,  
 2 
 }, { 
 1 
 ,  
 3 
 }}; 
 
 
      
 int 
  budget =  
 10 
 ; 
 
 
 
 
      
 int 
  result = maxProfit(n, present, future, hierarchy, budget); 
 
 
     cout << result << endl;  
 // 输出与 Go 程序一致 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。