华为机试原题8.18

题目1：喜爱值最大
第一行：输入总金钱money，商品数量n
此后的n行：（每行代表一个商品，数值分别代表，商品价格、商品可买数量、商品喜爱值）
商品价格商品数量商品喜爱值
p1 n1 like1
p2 n2 like2
...
问：如何购买能让喜爱值最大
题目2：商品综合
第一行：手中金钱为money，商品数量为n
第二行：商品的价格表例如[3, 7, 5, 10, 5]
问：选择某些商品，使得价格正好为money（商品不可重复选择，价格相同的算不同商品）
题目3；连连看
给定一个矩阵，例如
mat = [[1, 0, 2, 0, 3],
[0, 2, 0, 1, 1],
[0, 3, 0, 0, 0]]
给定两点例如：a点位（0，2）b点为（1，1）

问：两点间的路径，最短由几条直线组成（连线只能通过mat中为0的点，其余点为障碍）

第一题参考答案

total, kind_num = [int(x) for x in input().split()]
price = [0] * kind_num
num = [0] * kind_num
like = [0] * kind_num
for i in range(kind_num):
    price[i], num[i], like[i] = [int(x) for x in input().split()]

# 把商品按照数量展平放入 weight val数组 变成背包问题
commodity_num = sum(num)
weight = [0] * commodity_num
val = [0] * commodity_num

# price -> weight  like -> val
cnt = 0
for i in range(kind_num):
    p1, n1, l1 = price[i], num[i], like[i]
    while n1 > 0:
        n1 -= 1
        weight[cnt] = p1
        val[cnt] = l1
        cnt += 1
        
#dp shape为 （commodity_num+1）*(total+1)
dp = [[0] * (total + 1) for _ in range(commodity_num+1)]

for i in range(1, commodity_num + 1):
    weight_one, val_one = weight[i - 1], val[i - 1]
    for j in range(1, total + 1):
        if j >= weight_one:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_one] + val_one)
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[commodity_num][total])

第二题参考答案

# total为目标商品总价 kind_num为商品数量  price为价目表
total, kind_num = [int(x) for x in input().split()]
price = [int(x) for x in input().split()]

min_pri = min(price)
if total < min_pri:
    print(-1)
else:
    # dp shape为 （kind_num+1）*(total+1)
    # dp[i][j] 意思为 可选商品为 1~i 时候 总价为j 的可组合数量
    dp = [[0] * (total + 1) for _ in range(kind_num + 1)]

    # 把第一列置为 1
    for i in range(kind_num + 1):
        dp[i][0] = 1

    for i in range(1, kind_num + 1):
        val = price[i - 1]
        for j in range(1, total + 1):
            if j >= val:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - val]
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[kind_num][total])

第三题参考答案：

#3333333333
def search(ans, one_path, mat, vis, x_end, y_end, x_cur, y_cur, m, n):
    # 如果到了这个点 无需进行下方的一系列判断 直接认为成功到达 记录结果
    if x_cur == x_end and y_cur == y_end:
        one_path.append([x_cur, y_cur])
        ans.append(one_path.copy())  # 这里一定用copy 否则 one_path.pop的时候 ans里的也被修改了
        one_path.pop(-1)  # x_end y2点仅仅使用一次 记录完答案立即pop出去
        return

    # 若不是目的地 检查 边界 是否可走 mat==0  是否已经visit 过
    if x_cur < 0&nbs***bsp;x_cur >= m&nbs***bsp;y_cur < 0&nbs***bsp;y_cur >= n&nbs***bsp;mat[x_cur][y_cur] != 0&nbs***bsp;vis[x_cur][y_cur] == True:
        return

    # 不越界 可走 未visi 进行下一步
    vis[x_cur][y_cur] = True
    one_path.append([x_cur, y_cur])

    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur - 1, y_cur, m, n)  # 上
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur + 1, y_cur, m, n)  # 下
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur, y_cur - 1, m, n)  # 左
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur, y_cur + 1, m, n)  # 右

    one_path.pop(-1)
    vis[x_cur][y_cur] = False
    return


def check_onepath(one_path):
    if len(one_path) < 2:
        return 0
    # 至少有两个点 先确定开始的方向
    x_direction = one_path[1][0] - one_path[0][0]
    y_direction = one_path[1][1] - one_path[0][1]
    num_of_lines = 1  # 初值为1 至少有一个方向

    for i in range(2, len(one_path)):
        # 判断当前方向
        delta_x = one_path[i][0] - one_path[i - 1][0]
        delta_y = one_path[i][1] - one_path[i - 1][1]

        if delta_x == x_direction and delta_y == y_direction:
            continue
        else:
            # 如果方向不一致 更改方向
            x_direction = delta_x
            y_direction = delta_y
            num_of_lines += 1
    return num_of_lines


def check_ans(paths):
    result = []
    for one_path in paths:
        num_of_lines = check_onepath(one_path)
        result.append(num_of_lines)
    return min(result)


m, n = [int(x) for x in input().split()]

mat = [[0] * n for _ in range(m)]
vis = [[False] * n for _ in range(m)]
ans = []

for i in range(m):
    mat[i] = [int(x) for x in input().split()]

x1, y1, x2, y2 = [int(x) for x in input().split()]

# 初始化部分量 x1 y1点开始 所以这个点设为True 否则有问题
vis[x1][y1] = True
one_path = [[x1, y1]]

# 手动尝试从四个点开始搜索 要不然都放在search里判断就麻烦了
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1 - 1, y_cur=y1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1 + 1, y_cur=y1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1, y_cur=y1 - 1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1, y_cur=y1 + 1, m=m, n=n)

result = check_ans(ans)
print(result)