背包问题

背包问题是算法中的经典问题，尤其是在动态规划中应用广泛。以下是一些 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

  • 将一堆石头分成两组，使得两组的重量差最小。