Python考试999+编程题---实例+诡异版---持续更新中
第一题：背包问题（01背包）
题目：有 n 个物品和一个最多能承受重量为 w 的背包。第 i 个物品的重量是 weight [i]，价值是 value [i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大
思路：
①定义 dp [j] 表示容量为 j 的背包能装的最大价值
②状态转移方程：dp [j] = max (dp [j], dp [j - weight [i]] + value [i])
③遍历顺序：先遍历物品，再倒序遍历背包容量（避免重复选取同一物品）
def knapsack_01(weight: list[int], value: list[int], w: int) -> int: n = len(weight) dp = [0] * (w + 1) for i in range(n): for j in range(w, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) return dp[w] # 测试 weight = [1, 3, 4] value = [15, 20, 30] w = 4 print(knapsack_01(weight, value, w)) # 输出: 35第二题：完全背包问题
题目：有 n 个物品和一个最多能承受重量为 w 的背包。第 i 个物品的重量是 weight [i]，价值是 value [i]。每件物品可以无限次使用，求解将哪些物品装入背包里物品价值总和最大。
思路：
①与 01 背包的区别在于物品可以重复选取
②状态转移方程与 01 背包相同：dp [j] = max (dp [j], dp [j - weight [i]] + value [i])
③遍历顺序：先遍历物品，再正序遍历背包容量（允许重复选取同一物品）
def knapsack_complete(weight: list[int], value: list[int], w: int) -> int: n = len(weight) dp = [0] * (w + 1) for i in range(n): for j in range(weight[i], w + 1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) return dp[w] # 测试 weight = [1, 3, 4] value = [15, 20, 30] w = 4 print(knapsack_complete(weight, value, w)) # 输出: 60第三题：分割等和子集
题目：给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：
①转化为 01 背包问题：是否能从数组中选出一些元素，使得它们的和等于总和的一半
②首先计算数组总和，如果是奇数直接返回 False
③定义 dp [j] 表示是否能组成和为 j 的子集
④状态转移方程：dp [j] = dp [j] or dp [j - nums [i]]、
def canPartition(nums: list[int]) -> bool: total_sum = sum(nums) if total_sum % 2 != 0: return False target = total_sum // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[target] # 测试 print(canPartition([1,5,11,5])) # 输出: True print(canPartition([1,2,3,5])) # 输出: False第四题：不同路径
题目：一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
思路：
①定义 dp [i][j] 表示到达 (i,j) 位置的不同路径数
②状态转移方程：dp [i][j] = dp [i-1][j] + dp [i][j-1]
③边界条件：第一行和第一列的所有位置路径数都是 1
def uniquePaths(m: int, n: int) -> int: dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1] # 测试 print(uniquePaths(3, 7)) # 输出: 28 print(uniquePaths(3, 2)) # 输出: 3第五题：小写字母转大写字母
题目：从键盘输入一个字符串，将小写字母全部转换成大写字母，然后输出到一个磁盘文件“test”中保存
输入的字符串以！结束
if_name_=="__main__" fp=open("test.txt","w") string=raw_input("please input a string:\n") string=string.upper() fp.write(string) fp=open("test.txt","r") print fp.read() fp.close()