算法刷题Day 42 背包问题理论基础+分割等和子集

**算法刷题 Day42: 背包问题理论基础 + 分割等和子集**

今天，我们将讨论一个经典的算法问题——背包问题（Knapsack Problem）。这个问题是许多算法竞赛中常见的一个基本问题。我们还会介绍另一个相关的问题——分割等和子集。

**1. 背包问题**

背包问题是一种经典的0-1背包问题，描述如下：

假设有 n 个物品，每个物品都有一个重量（weight）和价值（value）。我们有一个背包，可以容纳总重量不超过 W 的物品。我们的目标是选择哪些物品放入背包，使得背包中的物品的总价值最大。

**1.1 背包问题的数学模型**

假设有 n 个物品，每个物品都有一个重量（weight）和价值（value）。我们可以将这些信息表示为一个二维数组：

| 物品序号 | 重量 |价值 |
| --- | --- | --- |
|1 | w1 | v1 |
|2 | w2 | v2 |
| ... | ... | ... |
| n | wn | vn |

我们还需要一个背包容量 W。

**1.2 背包问题的算法**

背包问题可以使用动态规划（Dynamic Programming）来解决。动态规划是一种通过分解大问题为小子问题来求解的大规模优化技术。

我们可以创建一个二维数组 dp，大小为 (n+1) x (W+1)，其中每个元素 dp[i][j] 表示前 i 个物品中能放入重量不超过 j 的背包中的最大价值。

**代码示例**

def knapsack(weights, values, W):
 n = len(weights)
 dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

 for i in range(1, n+1):
 for j in range(1, W+1):
 if weights[i-1] <= j:
 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
 else:
 dp[i][j] = dp[i-1][j]

 return dp[n][W]

def canPartition(nums):
 n = len(nums)
 total_sum = sum(nums)
 if total_sum %2 !=0:
 return False target_sum = total_sum //2 dp = [[0 for _ in range(target_sum +1)] for _ in range(n +1)]

 for i in range(1, n+1):
 for j in range(1, target_sum +1):
 if nums[i-1] <= j:
 dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] +1)
 else:
 dp[i][j] = dp[i-1][j]

 return dp[n][target_sum] >0