优化2^n复杂度的苹果采摘递归算法,满足100棵树/24300个篮子的3秒计算要求
算法优化方案
原实现的核心问题
- 全局HashMap缓存完全无效:不同篮子的初始容量C、伸缩属性F完全独立,跨篮子的状态没有复用价值,拼接字符串做缓存键的设计占用了大量冗余内存,直接触发MLE
- 递归式实现效率极低:频繁的函数栈调用、参数传递开销大,且递归分支没有做有效剪枝,无缓存时分支数指数级膨胀触发TLE
- 递归逻辑存在硬伤:采摘分支的递归调用遗漏了
basketFlex参数,递归过程中伸缩属性值丢失,实际计算结果和预期逻辑完全不一致
优化核心思路
将原来的指数级递归替换为带帕累托剪枝的迭代动态规划,彻底淘汰HashMap缓存,把内存占用降到最低,同时将时间复杂度压到时效要求内。
1. 全局资源复用
所有树的苹果数数组A是全局固定的,仅在内存中存一份,不需要在计算每个篮子时重复初始化。
2. 状态设计重构
放弃把“剩余容量”当缓存键的设计,每个篮子计算时仅用两个临时一维数组逐树迭代推进,处理完当前层就释放上一层的内存,完全不需要跨层存储:
- 定义
prev[k]数组:处理完前i棵树、累计完成k次扩张时,存储所有不被支配的有效状态(每个状态记录两个值:累计采摘的苹果数S、剩余可采摘容量R) - 支配剪枝规则:对同一个i、同一个k下的两个状态(S1, R1)和(S2, R2),如果满足S1 >= S2且R1 >= R2,状态(S2, R2)可直接丢弃——这个状态下采摘的苹果更少、剩余容量还更低,后续不管怎么选都不可能比(S1, R1)的结果好,属于完全无效的冗余状态
3. 逐树状态转移逻辑
从i=0(未处理任何树,初始状态为k=0,S=0,R=初始容量C)开始,逐棵树做状态转移:
- 对每个k对应的有效状态,分两种操作计算下一层的状态
- 扩张操作:不采摘当前树的苹果,累计扩张次数变为k+1,剩余容量变为R + F,累计采摘S不变,直接存入下一层对应k+1的状态列表
- 采摘操作:如果当前剩余容量R >= 当前树的苹果数A[i],则采摘当前树,累计采摘S变为S + A[i],剩余容量变为R - A[i],累计扩张k不变,存入下一层对应k的状态列表
- 下一层所有k的状态收集完成后,立刻执行帕累托剪枝,删掉被支配的无效状态,仅留有效状态进入下一轮转移
4. 性能与内存估算
单篮子的计算量最多为100棵树 * 最多100种扩张次数k * 剪枝后每个k平均1-2个有效状态 = 约2e4次简单整数操作
24300个篮子的总操作量约为4.8e8次,全程都是连续内存的数组访问,没有哈希计算、没有字符串拼接、没有递归栈开销,Java环境下3秒内完全可以跑完。
内存方面,每次计算仅保留两层的状态数组,总内存占用不到1MB,完全不会触发MLE。
优化后的Java参考实现
public class BasketPicker { // 全局共享的苹果树数组,仅初始化一次 private static int[] appleTrees; public static int calculateMaxApples(int initialC, int flexF) { int n = appleTrees.length; // 用long打包状态:高32位存剩余容量R,低32位存累计采摘S,减少对象开销 ArrayList<Long>[] prev = new ArrayList[n+1]; for (int i = 0; i <= n; i++) { prev[i] = new ArrayList<>(); } // 初始状态:未处理任何树,0次扩张,0个采摘量,剩余容量为C prev[0].add( ((long)initialC << 32) ); for (int i = 0; i < n; i++) { ArrayList<Long>[] curr = new ArrayList[n+1]; for (int j = 0; j <= n; j++) { curr[j] = new ArrayList<>(); } int currentApple = appleTrees[i]; // 遍历上一层所有有效状态 for (int k = 0; k <= i; k++) { for (Long state : prev[k]) { long R = (state >> 32) & 0xFFFFFFFFL; long S = state & 0xFFFFFFFFL; // 操作1:扩张当前树 long newR = R + flexF; curr[k+1].add( (newR << 32) | S ); // 操作2:满足容量条件时采摘当前树 if (R >= currentApple) { long newR_pick = R - currentApple; long newS_pick = S + currentApple; curr[k].add( (newR_pick << 32) | newS_pick ); } } } // 对当前层每个k的状态做帕累托剪枝 for (int k = 0; k <= i+1; k++) { if (curr[k].isEmpty()) continue; // 按累计采摘量S从大到小排序 curr[k].sort((a,b) -> { long sa = a & 0xFFFFFFFFL; long sb = b & 0xFFFFFFFFL; return Long.compare(sb, sa); }); // 过滤掉被支配的状态:S更小、R也更小的状态直接删除 ArrayList<Long> filtered = new ArrayList<>(); long maxR = -1; for (Long state : curr[k]) { long R = (state >> 32) & 0xFFFFFFFFL; if (R > maxR) { filtered.add(state); maxR = R; } } curr[k] = filtered; } prev = curr; } // 遍历完所有树,找最大的累计采摘量 int maxS = 0; for (int k = 0; k <= n; k++) { for (Long state : prev[k]) { long S = state & 0xFFFFFFFFL; if (S > maxS) maxS = (int)S; } } return maxS; } }
内容的提问来源于stack exchange,提问作者James Friederich
相关产品推荐
相关产品推荐

