从一个京东的实习生招聘题目讨论算法的选择

摘要：生日礼物题目来源京东实习生招聘原题链接可在线提交赛码网题目描述的生日快到了，这一次，小东决定为送一份特别的生日礼物为其庆生。小东计划送一个生日卡片，并通过特别的包装让永远难忘。

最近2个月时间都比较忙，另外还有些其他的事情，几乎没有怎么做题和写文章了，害怕自己又开始懒散起来了，所以还是督促自己不断地学习和练习编码。最近还需要好好学下python面向对象的一些知识了。
今天我们来分析一个JD的2016实习生招聘题目，该题目在赛码网上标为5星难度，我认为这个题目的难点在于对题目的理解，并且如何在较短的时间内选择一个更佳的算法来完成coding。

<题目来源： 京东2016实习生招聘 原题链接-可在线提交(赛码网)>

BF的生日快到了，这一次，小东决定为BF送一份特别的生日礼物为其庆生。作为高智商中的佼佼者，BF在国外求学，因此小东无法与之一起庆生。小东计划送一个生日卡片，并通过特别的包装让BF永远难忘。
她决定把卡片套装在一系列的信封A = {a1,  a2,  ...,  an}中。小东已经从商店中购买了很多的信封，她希望能够用手头中尽可能多的信封包装卡片。为防止卡片或信封被损坏，只有长宽较小的信封能够装入大些的信封，同尺寸的信封不能套装，卡片和信封都不能折叠。
小东计算了邮寄的时间，发现她的时间已经不够了，为此找你帮忙包装，你能帮她吗？

首先根据样例确认题目要求。
这里我再给出一组样例数据并且给出正确输出来验证是否彻底理解题目要求：
5 1000 998
5002 5005
5003 5004
5003 5002
5002 5001
5002 5002
正确的输出是
2
4
2

注意到以下3个问题：
(1)题目要求的卡片必须是装入能装入且最小的一个信封
(2)如果有多个信封可以选择，那么选择先拿到手上的，也就是在样例中先出现的封信，具体可以参见我给出的那组样例输出，最后选择了2而不是3，就是以为在2，3都可用时，选择先出现的，也就是第2个封信
(3)信封不能旋转，但是这点似乎题目中并没有提及到

现在我们来讨论如何解决这个问题
由于信封要被一层一层的封装，并且要用到尽可能多的信封。得到的解如果是r[1], r[2], ... r[n]，那么满足r[i] < r[i + 1] ("<"表示左侧可以被右侧装下)，这有什么用呢？这提示我们需要对其进行一个整理，得到一个整理后的序列满足：
envelop[1], envelop[2], ... envelop[i], ... envelop[n]
envelop[j] !> envelop[i] (i > j) 其中("!>" 表示左侧能不右侧装下信封，>表示左侧可以装下右侧信封)
这样的话，我们可以考虑使用面积进行排序。因此面积大的不一定的下面积小的信封，但是面积小的一定装不下面积大的信封 。

在得到这样的一个具体拓扑关系(关于拓扑排序/结构，可以参考相关资料)序列之后，如果你对动态规划(DP)有所了解，似乎首先会想到最长不下降子序列(LIS)问题，因为在得到拓扑序列后，我们可以按这个序列来划分阶段，来进行动态规划。

设f[i]表示，如果选择i个信封来装可以最多使用的信封个数，同时设g[i]记录i的前一个使用的信封的下标。由于最后我们要输出信封的顺序编号，别忘记了带上原来的顺序编号，在拓扑排序的时候，我们可以在遇到多个入度为0的点时，优先选择编号较小的点加入拓扑序列，方便后续DP时的处理。
f[i] = max(f[j]) + 1, i > j and f[j] > 0 and envelop[i] > envelop[j]
g[i] = j (f[J] = f[i], j = min{J})
特别注意的是，由于有多个信封可用时需要选择编号较小的，计算g[i]时，当有多个f[j]都满足条件时，选择最小的那个j。
最后的答案是max(f[i])，最后一个选择是信封是i最小的那个。然后我们根据g[i]可以倒推出所有选择信封。

至此，问题得到了解决。

但是，我们再咨询观察得到的拓扑序列发现，当确定最开始的信封之后，如果envelop[i] < envelop[j]，并且j是第一个满足这个条件的信封，显然我们会选择j，因为后面的信封只存在两种情况，不能装下j，但是都比较j晚出现，不会选择。如果能把j装下，且第一个出现，我们依然会选择。反之，如果不按这个策略选择，显然不可能得到更好的解。
简单反证如下(如果用数学归纳法也类似):
现在有序列envelop[] 其中envelop[0]是最小能装入卡片的信封，envelop[i]是第一个可以装下envelop[0]的信封，假设选择envelopj得到更优的解，那么存在两种情况：
1) envelop[j] > envelop[i]，这时加入envelop[i]显然可以使用多一个信封，与假设矛盾
2) envelop[j] !> envelop[j]，选择更早出现的i才符合题目要求，与假设矛盾

一些后话：
1.这个题目不一定每个人都会立刻想到使用类似LIS的算法，比如不会LIS，又比如一眼就能看出问题本质，使用更佳的解法。更多时候我们可能是一步一步进行算法的演进，然后再不断的进行更好的选择和优化。问题可以有多种正确解法，但是并不是每种正确解法都是最优的。

2.关于拓扑排序的方式有多种，我这里并没有使用基于图的方法，因为需要建图(O(n^2))在时间上相对我直接使用O(n^2)的插入排序的方法并没有优势。
具体实现的时候，我每次在原来的信封序列中取一个，放在已经得到的拓扑序列封信序列的第一个位置，然后和后一个比较，看是否需要交换，如果交换后，继续向后比较，不需要交换则比较结束，继续这个过程知道原来的信封已经取完
envelop a和envelop b交换的条件是：
envelop a > envelop b
or
envelop a !> envelop b and envelop a !< envelop b and Pa > Pb
其中Pa > Pb表示a在原给出的信封序列中位置更靠后

3.最后，在参考其他答案的时候，我也发现了一个O(nlogn)的算法，算法思想和我们提到的大致相同，他首选是按面积进行一个排序，然后仅通过O(n)的一次扫描就得到最后的答案，思想比较巧妙。有兴趣可以在题目链接的“正确答案”中查看。

4.此外，关于LIS算法以及优化可以参考以下文章:
http://blog.csdn.net/hulifang...
http://blog.csdn.net/wall_f/a...

import sys

const_w = 0
const_h = 1
const_p = 2


def is_swap(a, b):
    a_contain_b = True if a[const_w] > b[const_w] and a[const_h] > b[const_h] else False
    b_contain_a = True if a[const_w] < b[const_w] and a[const_h] < b[const_h] else False

    if a_contain_b or (not a_contain_b and not b_contain_a and a[const_p] > b[const_p]):
        return True
    return False


def sort(envelops):
    s_envelops = []
    for envelop in envelops:
        s_envelops.insert(0, envelop)
        for i in range(len(s_envelops) - 1):
            if is_swap(s_envelops[i], s_envelops[i + 1]):
                temp = s_envelops[i]
                s_envelops[i] = s_envelops[i + 1]
                s_envelops[i + 1] = temp
            else:
                break
    return s_envelops


def main():
    envelops = []

    while True:
        line = map(int, sys.stdin.readline().strip().split())
        if len(line) < 3:
            return

        n, w, h = line[0], line[1], line[2]

        for i in range(n):
            line = map(int, sys.stdin.readline().strip().split())
            envelops.append((line[0], line[1], i + 1))
        s_envelops = sort(envelops)

        card_in = -1
        min_area = sys.maxint
        for i, s_envelop in enumerate(s_envelops):
            if s_envelop[const_w] > w and s_envelop[const_h] > h and s_envelop[const_w] * s_envelop[const_h] < min_area:
                min_area = s_envelop[const_w] * s_envelop[const_h]
                card_in = i

        if card_in < 0:
            print 0
        else:
            cnt = 1
            results = [s_envelops[card_in][const_p]]
            last = s_envelops[card_in]
            for i in range(card_in + 1, n):
                if s_envelops[i][const_w] > last[const_w] and s_envelops[i][const_h] > last[const_h]:
                    cnt += 1
                    results.append(s_envelops[i][const_p])
                    last = s_envelops[i]

            print cnt
            for result in results:
                print result,
            print

        envelops[:] = []


        # for s_envelop in s_envelops:
        #     print s_envelop[const_w], s_envelop[const_h], s_envelop[const_p]


if __name__ == "__main__":
    main()