背包问题，使用动态规划求解。
分类
有 num 个物品和容量为 weight 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。
0-1 背包
每件物品只能选择拿或不拿。使用二维数组，dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。状态转移方程为
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) (if j >= w)
dp[i-1][j] (if j < w)
可以进行空间优化，使用一维的 dp 数组，内层需要逆向遍历。
def knapsack(weights: list[int], values: list[int], int weight_goal):
dp = [0 for _ in range(w + 1)]
for w in weights:
for j in reversed(range(w, weight_goal + 1)):
# ^^^ 逆向遍历
dp[j] = max(dp[j], dp[j-w] + values[i])
return dp[weight_goal]
完全背包
相关题目
0-1 背包：LeetCode 474. Ones and Zeroes
TODO
添加代码