【ACM】—蓝桥杯大一暑期集训Day3

**ACM — 蓝桥杯大一暑期集训 Day3**

### **一、前言**

在前两天的集训中，我们已经学习了基本的算法思想和数据结构。今天，我们将继续深入探讨这些主题，并且开始接触一些更复杂的问题。

### **二、动态规划**

#### **2.1什么是动态规划?**

动态规划（Dynamic Programming）是一种解决问题的方法，通过分解一个大问题为多个小问题，然后逐步求解这些小问题，最终得到原问题的答案。这种方法特别适用于有重叠子问题的递归问题。

#### **2.2 动态规划的特点**

动态规划的特点是：

*问题可以分解为多个子问题* 子问题之间存在重叠* 每个子问题的答案只需要计算一次#### **2.3 动态规划的步骤**

动态规划的步骤是：

1. 分解原问题为多个子问题2. 逐步求解这些子问题3. 使用之前计算过的结果来避免重复计算### **三、背包问题**

#### **3.1什么是背包问题?**

背包问题是一种经典的动态规划问题。假设有一个背包，容量为 `W`，有 `n` 个物品，每个物品的重量和价值分别为 `(w[i], v[i])`。要求求出在不超过背包容量的情况下，能获得的最大价值。

#### **3.2 背包问题的动态规划**

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

 for i in range(1, n +1):
 for j in range(1, W +1):
 if w[i -1] > j:
 dp[i][j] = dp[i -1][j]
 else:
 dp[i][j] = max(dp[i -1][j], dp[i -1][j - w[i -1]] + v[i -1])

 return dp[n][W]

# 测试w = [2,3,4,5]
v = [10,20,30,40]
W =7print(knapsack(W, w, v)) # 输出:60