本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing2 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背包【代码详解】// 朴素解法#includebits/stdc.husingnamespacestd;constintN1005;// 最大物品数和背包容量intn,m;// n: 物品数量, m: 背包容量intv[N],w[N];// v[i]: 第i件物品的重量, w[i]: 第i件物品的价值intf[N][N];// f[i][j]: 前i件物品总重量不超过j的最大价值intmain(){// 输入物品数量和背包容量cinnm;// 输入每件物品的重量和价值// 注意物品编号从1开始方便理解for(inti1;in;i){cinv[i]w[i];// 输入第i件物品的重量和价值}// 动态规划填表// i: 考虑前i件物品// j: 当前背包可用容量for(inti1;in;i)// 遍历每件物品{for(intj0;jm;j)// 遍历所有可能的背包容量{// 不选第i件物品的情况f[i][j]f[i-1][j];// 如果能选第i件物品当前容量j ≥ 物品i的重量v[i]if(jv[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时的最大价值coutf[n][m]endl;return0;}// 一维数组优化版#includebits/stdc.husingnamespacestd;constintN1005;// 最大物品数和背包容量intn,m;// n: 物品数量, m: 背包容量intv[N],w[N];// v[i]: 第i件物品的重量, w[i]: 第i件物品的价值intf[N];// f[j]: 容量为j时的最大价值优化为一维数组intmain(){// 输入物品数量和背包容量cinnm;// 输入每件物品的重量和价值// 注意物品编号从1开始方便理解for(inti1;in;i){cinv[i]w[i];// 输入第i件物品的重量和价值}// 动态规划填表// 外层循环遍历每件物品for(inti1;in;i){// 内层循环反向遍历背包容量// 必须从大到小遍历确保每个物品只被选一次for(intjm;jv[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时的最大价值coutf[m]endl;return0;}【运行结果】4 5 1 2 2 4 3 4 4 5 8