算法

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) @ca