You need to enable JavaScript to run this app. 优化2^n复杂度的苹果采摘递归算法,满足100棵树/24300个篮子的3秒计算要求
优惠活动
大模型
产品
解决方案
定价
更多

优化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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.21 09:54:03