资源规划问题

问题可以简述为：

1. 每项资源i总共被访问的次数为n_i
2. 每项资源i的容积为v_i，仓库总共可容纳的总容积为V
3. 每项资源i不从仓库取需消耗资源为w_i，从仓库取需消耗资源为t_i，且0 < v_i < w_i

4. 平均获取资源总资源消耗为（记仓库集为C，历史总访问次数为N = \sum n_i）：

   
   
   

   求当T最小时C中元素集{i}。

记不走仓库时的总资源消耗为：

则有：

从而，让T中减除部分最大的C就是满足要求的C。

因此，问题本身其实可以被改述为：

1. 每个项目i有 v_i 和 w_i 两个参数
2. 求在 V_C = \sum_{i \in C} v_i <= V 的约束下令 W_C = \sum_{i \in C} w_i 最大的集合C

记集合C的总容积为V_C = \sum_{i \in C} v_i，余容积为：V'_C = V - V_C。

假定，已有集合C={i}，如果其中存在子集c={k}以及C补集中的子集p={l}$，满足：

则将c与p交换后的新集合C'显然比原来的C更满足上述要求。

如果将所有可能的情况都考虑进去，那么对于一个拥有N个元素的上述问题，需要的计算量大约为2^N，显然把所有子集都遍历一遍是一个非常耗时的方法，虽然可以找到全局最优解。

这种穷举法显然很没效率，我们需要想出更有的方案，即便找不到全剧最优解，也要设法找出质量较高的局部最优解。

从上面寻找全局最优的方法中我们可以发现，项目消耗的资源越多，那么它被放入仓库的权重越高，同时它的容积越大权重理应越小。

因此，一个比较快速的局部最优方案可以是取如下形式的权重，并以该权重做降序排列，以此获得一个序列：

当选择恰当的omega时，我们期望可以对各种分布的 v_i 和 w_i 都能获得较满意的结果。

测试发现，当omega 在 [0.8, 1.2]这个范围时，对于大部分情况上述函数可以达到一个峰值。

而计算量方面，对于N个元素的问题，计算权重需要 O(N) 次，排序需要 O(N ln N) 次，所以总计算量是 O(N ln N) 量级。

以node.js不启用线程与进程为例，10000个元素的情况下，上述问题找到局部最优解耗时约在20ms量级。

当然，行数一次排序后当然只是得到一个局部最优解，而且这个局部依赖于算法本身和所取的权重参数 omega 。

在上述排序法的基础上，我们可以做一次优化，对排序法得到的结果C做一次遍历，将其中的一个元素取出，并将C的补集中的若干元素插入，如果不超过总容积又能将总耗资提升，则将结果更换为这个新序列，这样的计算量约为 O(V N) 。

假如对于上述一次优化后的结果再做一次优化，直到第n+1次优化结果与第n次优化结果相同才作为最终结果输出（这还不是上面提到的寻找全局最优的穷举法），那么在最糟糕的情况下需要的计算量接近 O(V² N²) ，也是非常可观。所以不推荐这么做。

以10000个元素，总容积300，项目容积在10以下，这么个情况，耗时大约在2.6s的量级，而提升的总容积约为0.1%。

当然，我们可以取一个截断，以降低计算量：

对C的补集中的元素做一个加权排序，排序权重的形式和上面的 pⁱ
相同，但可以选择不同的权重参数，将容积小的排序靠前，然后对这个补集做阶段，只保留前L项，那么我们所需的计算量就可以控制在 O(V L) 的量级，从而速度可以大幅提升。

还是10000个元素、300容积的情况，截断数取100，那么计算耗时为600ms量级，总容积提升率也接近0.1%。

当然我们也可以采用另一种截断，即不对补集做截断而是对优化的递归深度做截断，那么此时在最差情况下的计算量接近为 O(V N L) ，最糟糕的情况下接近 O(V N² L) ，依然无法忍受。

只还只是一阶优化，即我们一次只替换原有C中的一个元素。我们还可以使用二阶优化，一次替换C中的两个元素，那么此时的计算量将从 O(V N) 提升为 O(V² N²) ，即便做截断也需要 O(V² L²) 的计算量，对于大V和大N很难忍受。

所以，在快速近似算法方面，推荐上述加权排序法，并配合上带截断的一次一阶优化。

除此之外，我们当然可以采用其他算法，比如蚁群算法、退火算法和遗传算法。

上述排序权重函数的形式并不唯一，我们当然可以考虑更多形式的权重函数，从而给出更高效的方案。

一般而言，排序权重函数可以记为：

这个排序函数不单单只是单个项目的参数的函数，还可以是整个参数集的函数。

进而，可以考虑使用机器学习的方法来给出优化，找到最好的、适配各种问题的排序权重函数，且学习完之后的计算量和排序算法一样只需要 O(N ln N) 的量级。

输入为 { v_i, w_i } ，而输出为排序权重 p_i ，训练函数就是排序后取总耗资，越大效果越优。显然对每一个i，算法本身应该是没有差别的，差别仅体现在值上，所以可以使用CNN做多层卷积来进行机器学习。