本文共 2540 字，大约阅读时间需要 8 分钟。
要给两个好友分西瓜，使两堆的质量差最小。每个西瓜的重量已知。
思路：使用动态规划求所有可能的子集和，找出最接近总重量的一半的那个和，两堆差值最小。
解决方案代码：
def min_difference(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 w = [int(input[ptr + i]) for i in range(N)] sum_all = sum(w) target = sum_all // 2 max_mask = 1 << N dp = [float('inf')] * (max_mask) dp[0] = 0 for mask in range(max_mask): if dp[mask] == float('inf'): continue s = dp[mask] for i in range(N): if not (mask & (1 << i)): new_mask = mask | (1 << i) new_s = s + w[i] diff = abs(sum_all - 2 * new_s) if diff < dp[new_mask]: dp[new_mask] = diff min_diff = min(dp) print(min_diff)min_difference() 解释：
在二维地图中，计算连通的水池数量。每个水池周围的4个方向相邻的水池属于同一池。
思路：使用BFS或DFS遍历每个地图中的水池，标记已访问的水池，统计不同连通区域的数量。
解决方案代码：
import sysfrom collections import dequedef count_water_pools(): input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): m = int(input[ptr]) n = int(input[ptr + 1]) ptr +=2 grid = [] for i in range(m): row = list(map(int, input[ptr:ptr+n])) ptr +=n grid.append(row) visited = [ [False for _ in range(n)] for __ in range(m)] count = 0 for i in range(m): for j in range(n): if grid[i][j] == 1 and not visited[i][j]: count +=1 # BFS q = deque() q.append( (i,j) ) visited[i][j] = True while q: x, y = q.popleft() for dx, dy in [ (-1,0), (1,0), (0,-1), (0,1) ]: nx = x + dx ny = y + dy if 0 <= nx < m and 0 <= ny < n: if grid[nx][ny] ==1 and not visited[nx][ny]: visited[nx][ny] = True q.append( (nx, ny) ) print(count)count_water_pools()
解释：
这两个问题通过动态规划和图遍历分别解决，分别找到最优的分组方式和连通的水池数量。
转载地址：http://pugzk.baihongyu.com/