Cacher is the code snippet organizer for pro developers

#!/usr/bin/python
# coding=utf-8


n = 10            # 有多少张票
a = [0] * (n+1)   # a[i]表示前i张票能获得的优惠最大值
applies = [[]] * (n+1)  # applies[i]：前i张票获得最大优惠时采用的所有套票规则
rules = [(2,10), (3,14), (4,22), (5,23)]    # 套票规则，买2优惠10 etc.

def test():
    for i in range(1,n+1):
        a[i] = a[i-1]   # 初始不用套票规则
        for j in range(len(rules)):
            ruleN, ruleV = rules[j]
            if i >= ruleN:
                old = a[i]
                a[i] = max(a[i-ruleN] + ruleV, old)
                # 记录应用的规则
                if old != a[i]:
                    applies[i] = applies[i-ruleN][:]
                    applies[i].append(rules[j])

if __name__ == "__main__":
    test()
    print a
    print applies
    #[0, 0, 10, 14, 22, 24, 32, 36, 44, 46, 54]
    #[[], [], [(2, 10)], [(3, 14)], [(4, 22)], [(3, 14), (2, 10)], [(4, 22), (2, 10)], [(4, 22), (3, 14)], [(4, 22), (4, 22)], [(4, 22), (3, 14), (2, 10)], [(4, 22), (4, 22), (2, 10)]]