本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程小明的U盘【题目描述】在 2202 年的某一天小明得到了一个高端 U 盘。但是小明发现这个 U 盘有一些问题这个 U 盘的传输接口大小是L LL只能传输大小不超过L LL的文件。这个 U 盘容量是S SS一共只能装不超过S SS的文件。但是他要备份的资料却有很多你只能备份其中的一部分。共有n nn个文件第i ii个文件的大小和价值为w i , v i w_i,v_iwi,vi。小明很快发现他不可能把所有文件装进优盘好在这是一个高端的 U 盘他可以花钱升级接口大小、或者升级容量。每花1 11元可以将接口大小增加1 11每花1 11元可以将 U 盘容量增加1 11。注意你的文件不能被分割你只能把一个文件整个的传输进去并储存在U盘中你放在 U 盘中文件的总大小不能超过 U 盘容量。现在问题来了小明只有m mm元他想知道他最多可能将多大价值的文件放入 U 盘中。【输入】第1 11行4 44个正整数n , m , L , S n,m,L,Sn,m,L,S。第2 22行n nn个正整数w 1 , w 2 , ⋯ , w n w_1,w_2,⋯ ,w_nw1,w2,⋯,wn。第3 33行n nn个正整数v 1 , v 2 , ⋯ , v n v_1,v_2,⋯ ,v_nv1,v2,⋯,vn。【输出】1 11个整数最多可以放入 U 盘的文件总价值。【输入样例】5 9 4 4 6 9 9 5 6 8 7 9 1 5【输出样例】9【核心思想】问题分析给定n nn个文件大小w i w_iwi价值v i v_iviU盘初始接口大小L LL、容量S SS预算m mm元。每花1元可将接口或容量增加1。文件大小必须同时满足不超过接口大小才能传输和不超过U盘容量才能存储。可以选择升级接口使某个大文件能够传输求在预算内能装入的最大总价值。这是一个01背包变体问题关键在于枚举哪个文件享受接口升级优惠。算法选择01背包dp[i][j]表示前i ii个文件花费不超过j jj的最大价值枚举优惠券使用排序后枚举哪个文件使用接口升级关键步骤按大小排序将文件按w i w_iwi从小到大排序保证枚举时前面文件都能通过当前接口01背包DP总可用资金 初始容量S SS 预算m mmdp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])选或不选第i ii个文件枚举升级使用对于排序后的第i ii个文件升级接口后的实际大小cost max(w[i] - L, 0)升级后大小为L LL原大小w [ i ] w[i]w[i]需要升级w [ i ] − L w[i]-Lw[i]−L剩余容量给其他文件S m - cost答案更新ans max(ans, dp[i][S m - cost])时间/空间复杂度时间复杂度O ( n × ( S m ) n log n ) O(n \times (Sm) n \log n)O(n×(Sm)nlogn)排序O ( n log n ) O(n \log n)O(nlogn)背包O ( n × ( S m ) ) O(n \times (Sm))O(n×(Sm))空间复杂度O ( n × ( S m ) ) O(n \times (Sm))O(n×(Sm))01背包变体带优惠券抵扣的核心思想排序预处理按文件大小排序确保枚举时前面文件都能通过当前接口大小枚举策略枚举哪个文件使用接口升级优惠其余文件使用普通容量费用计算升级接口后的实际占用 max(原大小 - 接口大小, 0)容量分配总资源 初始容量 预算分配给升级文件和普通文件适用于带单一优惠选择的背包问题【算法标签】#01背包【代码详解】#includebits/stdc.husingnamespacestd;constintN505;intn,m,l,s,dp[N][20005],ans;// dp: 背包DP数组, ans: 最终答案structnode{intw,v;// w: 原价, v: 价值}a[N];// 按原价从小到大排序boolcmp(node x,node y){returnx.wy.w;}intmain(){cinnmls;for(inti1;in;i){cina[i].w;// 读取原价}for(inti1;in;i){cina[i].v;// 读取价值}sort(a1,an1,cmp);// 0/1背包计算前i个物品花费不超过j的最大价值for(inti1;in;i){for(intj1;jsm;j)// 总可用资金 初始资金s 优惠券价值m{dp[i][j]dp[i-1][j];// 不选第i个物品if(ja[i].w){// 选第i个物品dp[i][j]max(dp[i][j],dp[i-1][j-a[i].w]a[i].v);}}}// 枚举使用优惠券购买的商品ifor(inti1;in;i){// 使用优惠券后的实际花费原价 - 优惠券价值l但不能为负intcostmax(a[i].w-l,0);ansmax(ans,dp[i][sm-cost]);}coutans;return0;}【运行结果】5 9 4 4 6 9 9 5 6 8 7 9 1 5 9
