嘉然小姐与狗——从沙雕草图中学习简单的算法

大概两个星期以前，沙雕网友突然在沙雕群里发了一张沙雕草图，原图如下：

看到这张图，我第一反应是该沙雕群友这几天看一个大概是叫asoul的vtb看疯了，因为他最近发的表情都变成了这个vtb的魔怔表情。但仔细一看这图上居然是个算法题，于是写期末大作业已经同样写到魔怔的我决定试一试。

我们首先把这个魔怔的题干改成正常人看得懂的形式：小明一共上了n门课，其中第i门课的学分是vi，成绩是ci。现要求找出课程集合，使得总学分最高，且加权均分不低于d。

看到这个题目，我们首先就会自然而然地想到，先把所有分数>d的课都先拿走，毕竟这部分都是白赚来的学分，不拿白不拿。然后，在剩余所有分数<d的课中，挑拣到尽量多的学分，同时在均分逐渐下降的过程中，保证最终不低于d。这里的第一反应是采用分治法，即

getMaxTotal(int 当前编号i, Set 已经选择的课程集合s) {

    if(i>n) return s的学分总和，直接结束

    if(选了i之后，均分仍然大于d) return getMaxTotal(i+1,s.add(i))和getMaxTotal(i+1,s))中的较大者

    else return getMaxTotal(i+1,s))，因为第i个不能选了只能跳过

}

然后直接求getMaxTotal(1，空集)就能得出结果。

其实这个问题到这里已经结束了，但这个算法有一个问题，就是时间复杂度为O(2^n)，因为这个算法实际实现了一个二叉选择树。尽管在树的末端选择会逐渐减少（均分已经扣得差不多了），但并不会影响总的大O取值，而且一个“好的”题目的测试点是绝对不会给你这种不超时的机会的。这里要引用一句沙雕同学的语录，“指数复杂度的算法多少都沾点脑瘫”。为了避免我成为他口中的脑瘫，这里的算法亟需改进。

那么该怎么改进呢？实际上在算法中，有类很出名的题目叫做0-1背包问题，大意是农夫背着固定大小为V的包捡n块石头，每块石头的大小和价值都不同，最终在石头大小总和不超过V的情况下获取最大的总价值。这个问题猛一看和文章中的沙雕题很类似，但在这个题的解法中，算法通过维护一个“包剩余不同大小时，不同的n所能得到的最大价值”的n行V列的表，从而实现了数据的复用，通过浪费一定的空间复杂度（把算好的数先记下来），使得时间复杂度降为O(V*n)。

但在本题中，“包”相当于把所有分数>d的课都先拿走后的平均分，而包的状态并不像上述典型问题中那样是连续的V种，而是一共有2^n种，这样就完全绕回去了。实际上，我在刚看到这道题的时候就是卡在这里了，可能是因为当时正处于刚做完作业的半晕厥状态。

然而，其实解决办法也很简单，就是把加权平均分中的Σci乘到上面去就好了，实际上是做了一个数字游戏。

Σ(vici)/Σ(ci)>=d
Σ(vici)-dΣ(vi)>=0
Σ(vi(ci-d))>=0
Σ(va(ca-d))>=Σ(vb(d-cb))，其中ab是把i分为了两部分，a是分数大于d的部分，b是分数小于d的部分。此时式子的左半是背包，右半是石头，并且背包和石头的大小都是连续的。

至此，题目的解法应该算是结束了，但最终留下了一个小问题，就是假如有些项目的分数不是整数怎么办。举个栗子，假如有个nt老师给了一门课78.125分，那V的大小此时要相应扩大8倍。假如另一个老师给了80+π分，那就会让整个算法的复杂度又回到O(2^n)的原点。但是，真的会有这样的老师吗？

以上。