背包问题

番风About 1 min

背包问题是算法中的经典问题，尤其是在动态规划中应用广泛。以下是一些 LeetCode 上关于背包问题的题目，这些题目涉及了不同变种和难度的背包问题，非常适合练习：

1. 0/1 背包问题

LeetCode 416: Partition Equal Subset Sum
- 将数组分为两个和相等的子集。
LeetCode 494: Target Sum
- 通过为数组中的每个元素分配正负号，使得总和等于目标值。
LeetCode 474: Ones and Zeroes
- 给定由 0 和 1 组成的字符串数组，计算可以由最多 m 个 0 和 n 个 1 构成的字符串最大数量。

2. 完全背包问题

LeetCode 518: Coin Change 2
- 给定不同面额的硬币和一个总金额，计算有多少种不同的方法可以组合成这个金额。
LeetCode 322: Coin Change
- 给定不同面额的硬币和一个总金额，计算可以凑成总金额的最少硬币数。
LeetCode 377: Combination Sum IV
- 找出所有可以凑成目标和的组合，组合中可以多次使用同一个数字。

3. 多重背包问题

LeetCode 879: Profitable Schemes
- 给定 n 名成员和 minProfit 的利润，计算有多少种分配成员的方式，可以使得盈利不小于 minProfit。

4. 部分和问题

LeetCode 698: Partition to K Equal Sum Subsets
- 将数组分割成 k 个和相等的子集。

5. 其他变种

LeetCode 139: Word Break
- 给定一个字符串和一个单词字典，确定是否可以将字符串分割成一个或多个在字典中出现的单词。
LeetCode 1049: Last Stone Weight II
- 将一堆石头分成两组，使得两组的重量差最小。