算法

Hailin

取球博弈

题目描述两个人玩取球游戏。一共有 N 个球，每人轮流取球，每次可取集合 {n1, n2, n3} 中的任意数目。如果无法继续取球，则游戏结束。此时，持有奇数个球的一方获胜。如果两人都是奇数，则为平局。双方都采用最优策略，判断先手是否能赢。解题思路博弈 + 记忆化搜索，状态定义很关键。游戏涉及三个维度：剩余球数 num当前玩家持有的球数奇偶性 x1对方持有的球数奇偶性 x2轮到谁 i（先手/后手）用

算法

Hailin

蓝桥杯-砝码称重

2021蓝桥杯省赛 - 砝码操作砝码称重问题描述你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, ..., WN。请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。输入格式第一行包含一个整数 N。第二行包含 N 个整数 W1, W2, ..., WN。输出格式输出一个整数代表答案。样例输入3 1 4 6样例输出10参考答案# 蓝桥杯 - 砝码称重 n = int(

算法

Hailin

完全背包问题

完全背包问题 Python描述"""完全背包问题""" from functools import cache # 有n种物品，第i种物品的体积为w[i]，价值为v[i]，每种物品无限次重复选 # 求体积和不超过 capacity 时的最大价值 """选或者不选""" # 选：剩余容量减少w[i] # 不选：容量不变 """子问题""" # 在剩余容量为 c 时，从前 i 种物品中得到的最大

算法

Hailin

01背包问题

from functools import cache from typing import List """01背包问题""" """求方案数问题 总方案数：两个互斥方案相加""" def zero_one_knapsack(capacity: int, weights: list[int], values: list[int]): n = len(weights) @cac