PyTorch 内存优化：RAM 使用降低 20 倍
0/1 Knapsack Problem in PyTorch
在使用 PyTorch 构建机器学习模型时，内存规划至关重要。默认激活内存预算求解器 dp_knapsack 虽能工作，但在处理大规模计算图时往往因内存占用过高而崩溃。通过引入 dp_knapsack_sliding_hirschberg 这一新求解器，结合滑动窗口技巧与 Hirschberg 算法，我们成功将峰值内存占用降低了 20 倍。这意味着在 64GB 内存的机器上，原本只能处理 100 个操作的任务，现在能轻松应对 2000 个操作。此外，该方案还带来了约 37% 的运行时加速。如果你追求精确解且无法依赖 SciPy，只需简单配置 torch._functorch.config 即可启用这一优化，让模型训练不再受限于显存瓶颈。
如果你将默认的 torch._functorch.config.activation_memory_budget_solver 从 dp 改为 dp_knapsack_sliding_hirschberg，就能将内存规划期间的峰值 RAM 使用量降低 20 倍。
- 7scan
在实际应用中，解决 0-1 背包问题几乎总是应该使用“组合”算法。对于中等到大规模实例，它的速度很可能比上述任何方法都快几个数量级。相关代码和参考资料在此：https://hjemmesider.diku.dk/~pisinger/codes.html
- shoo
我对作者指出的基准背包算法的问题很好奇——即它耗尽了内存。
看起来 PyTorch 的各种背包实现（包括作者贡献的那个）都在这里：
https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...
例如，它似乎被用在这里：
https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...
盯着基准 dp_knapsack 代码看时，我立刻注意到的一点是，用来衡量内存的单位究竟是什么意思并不清楚。dp_knapsack 代码假设 memory 和 max_memory（即内存预算）是浮点数。dp_knapsack 内部会将这些浮点内存值乘以 10,000，然后四舍五入为整数，以量化内存值——量化后的 max_memory 值定义了动态规划表的一个维度大小，另一个维度则由物品数量决定。
从阅读 partitioners.py 的补丁来看，内存预算似乎应该是一个介于 0.0 到 1.0 之间的浮点数，而且每个物品的内存大概是相对于该内存预算进行归一化的？
如果是这样，且 dp_knapsack 被调用时 max_memory 为 1.0，那么对于 n 个物品会分配一个二维数组，同时分配 m=10,000 个量化内存值，形状为 (n+1, m+1)。因此，对于 100 个物品，这将是一个形状为 (101, 10001) 的数组——它填充的是 float32，所以每个元素 4 字节，那么表格所需的大小将是……大约 4MB。[…]
- TacticalCoder
0/1 背包是一个很棒的小问题，尤其是它的动态规划解法。
我现在可能记错了，但当我三十年前学习 0/1 背包问题时，我立刻想到的是，对于很多情况，你可以使用动态规划得到一个近似版本（占用更少的内存，因此，例如，能够装入内存），并证明你的解“与最优解的偏差不超过 1%”。不过我从未深入研究过，所以我可能记错了。
基本上，假设你需要对数量 1739、2989、3798 和 4233 等进行 0/1 背包求解：你可以例如将它们除以 10 然后向上取整，这样你就得到了 174、299、380 和 424，运行你的 0/1 背包动态规划解法所需的内存就少得多。而且你找到的最佳解保证与最优解的偏差不超过 x%。
大概是这样的。这行得通吗？有人听说过类似的东西吗？