哔哩哔哩-算法-笔经

一.单选题
1.字典树：
https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin

2.有两个样本点，第一个点为正样本,它的特征向量是(0,-1);第二个点为负样本,它的特征向量是(2,3),从这两个样本点组成的训练集构建一个线性SVM分类器的分类面方程是（ ）
x+2y=5
x-2y=5
x-y=2
x+y=3
正确答案：A

3.一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。
1
9
10
11
正确答案：A B C

4.以下分布里属于离散概率分布的是
正态分布
二项分布
泊松分布
几何分布
正确答案：B C D

5.有一个算法的递推关系式为：T(N) = T(2N/3) + 1，则该算法的时间复杂度为（）(^符号是幂的意思)
O(1)
O(N^log2(3) )
O(N^log3(2) )
O(logN)
O(N)
正确答案：D

master公式：T [n] = aT[N/b] + T (N^d)
解法：
①当d<logb a时，时间复杂度为O(n^(logb a))
②当d=logb a时，时间复杂度为O((n^d)*logn)
③当d>logb a时，时间复杂度为O(n^d)

二.编程题
题目描述
某次漫展，已知有n个打卡点，每个打卡点的活动需要m_i 分钟完成，完成后获得奖励点r_i,已经打卡过的点不能再去。
需要在规定m分钟内完成，尽可能多的收获奖励点，求获得最多的奖励点数。

输入描述:
第一行两个整数，打卡点的数量n和限制时间m
第2到1+n行，每行两个整数m_i，r_i
数字以空格分割，其中0< n<= 100，1<=m<=120，1<=m_i<=10，1<=r_i<=100

输出描述:
整数，最大的奖励点数

示例1
输入
4 6
2 4
2 35
1 43
2 10

输出
88

01背包问题 AC

cd = list(map(int,input().split()))
count=cd[0]
volume=cd[1]
weight=[]
value=[]
for _ in range(count):
    cc = list(map(int,input().split()))
    weight.append(cc[0])
    value.append(cc[1])


def bag(n,c,w,v):
    res=[[-1 for j in range(c+1)] for i in range(n+1)]
    for j in range(c+1):
        res[0][j]=0
    for i in range(1,n+1):
        for j in range(1,c+1):
            res[i][j]=res[i-1][j]
            if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
                res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
    return res[n][c]

print(bag(count,volume,weight,value))