本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P13018 [GESP202506 七级] 调味平衡 - 洛谷

【题目描述】

小 A 准备了 $n$ 种食材用来制作料理，这些食材依次以 $1,2,\dots ,n$ 编号，第 $i$ 种食材的酸度为 $a_i$，甜度为 $b_i$。对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度 $A$ 为放入食材的酸度之和，甜度 $B$ 为放入食材的甜度之和。如果料理的酸度和甜度相等，那么料理的调味是平衡的。

过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？

【输入】

第一行，一个正整数 $n$，表示食材种类数量。

接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示食材的酸度和甜度。

【输出】

输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。

【输入样例】

3
1 2
2 4
3 2

【输出样例】

8

【核心思想】

1. 问题分析：给定 $n$ 种食材，每种食材有酸度 $a_i$ 和甜度 $b_i$。需要选择若干食材使得料理的酸度之和 $A$ 等于甜度之和 $B$（调味平衡），在此约束下最大化 $A+B$。这是一个差值背包问题，关键在于将"酸度等于甜度"的约束转化为"差值之和为0"。

2. 算法选择：

   • 差值转换：设 $d_i=a_i-b_i$（差值），$s_i=a_i+b_i$（和值）
   • 问题转化：选择食材使 $\sum d_i=0$，最大化 $\sum s_i$
   • 带偏移量的01背包：使用偏移量处理负数差值，将差值范围映射到非负数组下标

3. 关键步骤：

   • 数据转换：对于每种食材，计算 $d_i=a_i-b_i$，$s_i=a_i+b_i$
   • 状态定义：f[i][j] 表示前 $i$ 个食材，差值为 $j-OFFSET$ 时的最大和值
   • 偏移量设置：OFFSET = 50000，将差值范围 $[-OFFSET,OFFSET]$ 映射到数组下标 $[0,2\times OFFSET]$
   • 初始化：f[0][OFFSET] = 0（差值为0时和值为0），其余为负无穷
   • 状态转移：
     • 不选食材 $i$：f[i][j] = f[i-1][j]
     • 选食材 $i$：f[i][j] = max(f[i][j], f[i-1][j-d[i]] + s[i])（要求 $j\ge d[i]$）
   • 答案获取：f[n][OFFSET] 即差值为0时的最大和值

4. 时间/空间复杂度：

   • 时间复杂度：$O(n\times M)$，其中 $M=2\times OFFSET=100000$
   • 空间复杂度：$O(n\times M)$，可优化至 $O(M)$（滚动数组）

5. 差值背包的核心思想：

   • 差值转换技巧：将"两个属性相等"的约束转化为"差值之和为0"
   • 偏移量处理：通过加偏移量将可能为负的差值映射到非负数组下标
   • 01背包模型：每个食材选或不选，目标是在差值约束下最大化和值
   • 适用于"两个属性相等约束下最大化和"的背包问题

【算法标签】

#普及 #01背包

【代码详解】

#include<iostream>
#include<cstring>
using namespace std;
const int N=105, M = 1000005 ;  // 定义最大物品数N和最大容量M
int n, f[N][M],d[N],s[N];  // 物品数n，DP数组f，差值数组d，和值数组s

int main(){
    memset(f,-0x3f3f3f,sizeof f);  // 初始化DP数组为极小值
    cin>>n;  // 输入物品数量
    f[0][50000]=0;  // 初始化基础状态，偏移量50000
    for (int i=1; i<=n; i++)  // 读取每个物品的数据
    {
        int a, b;  // 物品的两个属性
        cin >> a >> b;  // 输入a和b
        d[i] = a - b;  // 计算差值
        s[i] = a + b;  // 计算和值
    }
    for (int i=1;i<=n;i++)  // 遍历每个物品
    {
        for (int j=d[i];j<=100000;j++)  // 遍历所有可能的容量
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-d[i]]+s[i]);  // 状态转移方程
        }
    }
    cout<<f[n][50000];  // 输出结果
    return 0;  // 程序正常结束
}

【运行结果】

3
1 2
2 4
3 2
8