9.17 京东算法岗笔试题目分享

第一题

道具的魅力值

时间限制: 3000MS
内存限制: 589824KB

题目描述:

在某网络游戏中提供了一个道具库，在道具库中每种道具均有若干件(数量已知)，游
戏玩家购买一件道具将获得一 定的魅力值。
已知每种道具的价格和魅力值，请编写一个程序， 在总价格不超过某个上限的情况下使
得所购道具的魅力值之和达到最大。

输入描述

单组输入。
每组测试数据的输入有n+ 1行，n表示道具的种类。
第1行包含两个正整数，分别表示道具种类数n和总价值的上限p，两个数字之间
用空格隔开。(n<=100, p<= 10000)
第2行到第n+ 1行分别对应于第1种道具到第n种道具的信息，每1行包含三个正
整数，两个数字之间用空格隔开，三个正整数分别表示某一种道具的数量、单个
道具的价格和魅力值。

输出描述

每组测试数据的输出只有一行，即道具魅力值的最大和。

样例输入
3 10
2 2 3
1 5 10
2 4 12

样例输出
27

背包问题 python没能A掉超时了没找到原因直接换java抄了一遍

line = input().strip().split()
n, p = [int(x) for x in line]
items = []
for i in range(n):
    line = input().strip().split()
    items.append([int(x) for x in line])
dp = [0] * (p+1)

for j in range(n):
    for t in range(items[j][0]):
        for i in range(p, items[j][1]-1, -1):
            dp[i] = max(dp[i], dp[i-items[j][1]]+items[j][2])

print(max(dp))

第二题

王子与公主

时间限制: 3000MS
内存限制: 589824KB

题目描述:

在一个n行m列的二维地图中，王子的位置为(x1,y1),公主的位置为(x2,y2)。
在地图中设有-些障碍物，王子只能朝上、下、左、右四个方向行走，且不允许走出地
图也不允许穿越障碍物。
请编写一个程序判断王子是否可以顺利走到公主所在的位置。

输入描述

多组输入，第1行输入一个正整数T表示输入数据的组数。
对于每一组输入数据: 输入n+1行。
其中，第1行输入两个正整数n和m表示地图的大小，n为行数，m为列数。
(n<=100,m<=100)
接下来n行表示地图，每一行都有m个字符， 其中S表示王子的位置，E表示公主
的位置，':表示可以通行，'#'表示障碍物(不能通行)。

输出描述

针对每一组输入数据， 判断王子是否能够到达公主所在位置?如果可以输出
"YES"，否则输出"NO"。

样例输入
2
2 2
.E
S.
2 2
#E
S#

样例输出
YES 
NO

直接写个dfs做就通过了裸题

def dfs(graph, i, j):
    if i < 0 or j < 0 or i >= len(graph) or j >= len(graph[0]) or graph[i][j] == '#': return False
    if graph[i][j] == 'E': return True
    graph[i][j] = '#'
    res = dfs(graph, i+1, j) or dfs(graph, i-1, j) or dfs(graph, i, j+1) or dfs(graph, i, j-1)
    graph[i][j] = '.'
    return res

t = int(input().strip())
while t > 0:
    line = input().strip().split()
    n, m = [int(x) for x in line]
    graph = []
    for i in range(n):
        line = input().strip()
        graph.append(list(line))
    res = False
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'S':
                res = dfs(graph, i, j)
    if res: print("YES")
    else: print("NO")
    t -= 1

#笔试题目##京东#