本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2871 [USACO07DEC] Charm Bracelet S - 洛谷【题目描述】有N NN件物品和一个容量为M MM的背包。第i ii件物品的重量是W i W_iWi​价值是D i D_iDi​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量且价值总和最大。【输入】第一行物品个数N NN和背包大小M MM。第二行至第N 1 N1N1行第i ii个物品的重量W i W_iWi​和价值D i D_iDi​。【输出】输出一行最大价值。【输入样例】4 6 1 4 2 6 3 12 2 7【输出样例】23【核心思想】问题分析给定N NN件物品每件有重量W i W_iWi​和价值D i D_iDi​背包容量为M MM。每件物品只能选一次求在总重量不超过M MM的前提下能装入背包的最大总价值。这是一个经典的01背包问题。算法选择01背包一维滚动数组d p [ j ] dp[j]dp[j]表示背包容量为j jj时的最大价值逆序遍历容量保证每件物品只选一次关键步骤读取输入N , M N, MN,M和N NN件物品的( W i , D i ) (W_i, D_i)(Wi​,Di​)初始化d p [ 0.. M ] 0 dp[0..M] 0dp[0..M]001背包递推i ii从1 11到N NN对于j jj从M MM到W i W_iWi​逆序d p [ j ] max ⁡ ( d p [ j ] , d p [ j − W i ] D i ) dp[j] \max(dp[j],\ dp[j - W_i] D_i)dp[j]max(dp[j],dp[j−Wi​]Di​)输出d p [ M ] dp[M]dp[M]时间/空间复杂度时间复杂度O ( N ⋅ M ) O(N \cdot M)O(N⋅M)空间复杂度O ( M ) O(M)O(M)一维滚动数组01背包的核心思想选或不选对于每件物品只有两种状态——选占用W i W_iWi​容量获得D i D_iDi​价值或不选不占用容量价值不变逆序遍历保证唯一性容量从大到小遍历确保d p [ j − W i ] dp[j - W_i]dp[j−Wi​]是未选第i ii件物品时的状态避免同一件物品被重复选取最优子结构d p [ j ] dp[j]dp[j]仅依赖之前的状态满足无后效性适用于有限物品 容量约束 最大化价值类经典背包问题【解题思路】【算法标签】#普及- #01背包【代码详解】#includebits/stdc.husingnamespacestd;intn,m,w[4000],d[4000],dp[12890];intmain(){cinnm;// 输入n和mfor(inti1;in;i){// 输入n件无皮的重量和价值cinw[i]d[i];}for(inti1;in;i){// 01背包的模板滚动数组版for(intjm;jw[i];j--){dp[j]max(dp[j],dp[j-w[i]]d[i]);}}coutdp[m]endl;// 输出dp[m]return0;}【运行结果】4 6 1 4 2 6 3 12 2 7 23