本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：2 01背包问题 - AcWing题库
【题目描述】
有N NN件物品和一个容量是V VV的背包。每件物品只能使用一次。
第i ii件物品的体积是v i v_ivi，价值是w i w_iwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
【输入】
第一行两个整数，N , V N,VN,V，用空格隔开，分别表示物品数量和背包容积。
接下来有N NN行，每行两个整数v i , w i v_i,w_ivi,wi，用空格隔开，分别表示第i ii件物品的体积和价值。
【输出】
输出一个整数，表示最大价值。
【输入样例】
4 5 1 2 2 4 3 4 4 5【输出样例】
8【算法标签】
#01背包
【代码详解】
// 朴素解法#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大物品数和背包容量intn,m;// n: 物品数量, m: 背包容量intv[N],w[N];// v[i]: 第i件物品的重量, w[i]: 第i件物品的价值intf[N][N];// f[i][j]: 前i件物品，总重量不超过j的最大价值intmain(){// 输入物品数量和背包容量cin>>n>>m;// 输入每件物品的重量和价值// 注意：物品编号从1开始，方便理解for(inti=1;i<=n;i++){cin>>v[i]>>w[i];// 输入第i件物品的重量和价值}// 动态规划填表// i: 考虑前i件物品// j: 当前背包可用容量for(inti=1;i<=n;i++)// 遍历每件物品{for(intj=0;j<=m;j++)// 遍历所有可能的背包容量{// 不选第i件物品的情况f[i][j]=f[i-1][j];// 如果能选第i件物品（当前容量j ≥ 物品i的重量v[i]）if(j>=v[i]){// 选择第i件物品的情况// 价值 = 不选第i件物品时的价值 + 第i件物品的价值// 容量 = 当前容量j - 物品i的重量v[i]f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}}// 输出结果：前n件物品，背包容量为m时的最大价值cout<<f[n][m]<<endl;return0;}// 一维数组优化版#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大物品数和背包容量intn,m;// n: 物品数量, m: 背包容量intv[N],w[N];// v[i]: 第i件物品的重量, w[i]: 第i件物品的价值intf[N];// f[j]: 容量为j时的最大价值（优化为一维数组）intmain(){// 输入物品数量和背包容量cin>>n>>m;// 输入每件物品的重量和价值// 注意：物品编号从1开始，方便理解for(inti=1;i<=n;i++){cin>>v[i]>>w[i];// 输入第i件物品的重量和价值}// 动态规划填表// 外层循环：遍历每件物品for(inti=1;i<=n;i++){// 内层循环：反向遍历背包容量// 必须从大到小遍历，确保每个物品只被选一次for(intj=m;j>=v[i];j--){// 状态转移方程：// 1. 不选第i件物品：f[j]保持不变// 2. 选第i件物品：f[j - v[i]] + w[i]f[j]=max(f[j],f[j-v[i]]+w[i]);}}// 输出结果：容量为m时的最大价值cout<<f[m]<<endl;return0;}【运行结果】
4 5 1 2 2 4 3 4 4 5 8
