题目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)
全部评论
(9) 回帖