本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程超大容量背包【题目描述】有n nn个物品编号从1 11到n nn每个物品有一个重量w i w_iwi和价值v i v_ivi。Taro有一个背包容量为W WW他想要挑选一些物品装到背包里面要求选择的物品重量和不能超过W WW。Taro想知道他能获得的最大价值是多少【输入】第一行两个整数n ( 1 ≤ n ≤ 100 ) n(1≤n≤100)n(1≤n≤100)和W ( 1 ≤ W ≤ 10 9 ) W(1≤W≤10^9)W(1≤W≤109)。接下来n nn行每行两个整数w i ( 1 ≤ w i ≤ W ≤ 10 9 ) w_i(1≤w_i≤W≤10^9)wi(1≤wi≤W≤109)和v i ( 1 ≤ v i ≤ 10 3 ) v_i(1≤v_i≤10^3)vi(1≤vi≤103)表示第i ii个物品的重量和价值。【输出】输出一行包含一个整数表示Taro能获得的最大价值。【输入样例】3 8 3 30 4 50 5 60【输出样例】90【核心思想】问题分析给定n nn个物品重量w i w_iwi价值v i v_ivi和背包容量W WWW ≤ 10 9 W \leq 10^9W≤109求在重量不超过W WW的情况下能获得的最大价值。由于W WW很大10 9 10^9109无法使用常规的以重量为维度的DP。但价值v i ≤ 10 3 v_i \leq 10^3vi≤103且n ≤ 100 n \leq 100n≤100总价值上限为10 5 10^5105可以使用以价值为维度的逆向DP。算法选择逆向DPdp[j]表示获得价值j jj所需的最小重量维度转换将重量限制下的最大价值转化为价值目标下的最小重量关键步骤初始化dp[0] 0获得价值0需要重量0其余为无穷大状态转移逆序遍历价值j jj从v i v_ivi到总价值上限dp[j] min(dp[j], dp[j - v[i]] w[i])选或不选第i ii个物品统计答案从高到低遍历价值j jj找到第一个满足dp[j] W的j jj即为最大价值时间/空间复杂度时间复杂度O ( n × V t o t a l ) O(n \times V_{total})O(n×Vtotal)其中V t o t a l n × max ( v i ) ≤ 10 5 V_{total} n \times \max(v_i) \leq 10^5Vtotaln×max(vi)≤105空间复杂度O ( V t o t a l ) O(V_{total})O(Vtotal)一维数组01背包逆向DP的核心思想维度转换策略当重量范围大、价值范围小时将DP维度从重量转换为价值逆向思维dp[j]表示获得价值j jj所需的最小重量而非传统DP中重量j jj下的最大价值逆序遍历01背包的一维优化需要逆序遍历避免重复选择结果查找从高价值向低价值查找第一个满足重量约束的值即为答案适用于重量范围极大、价值范围较小的背包问题【算法标签】#01背包【代码详解】#includeiostream#includecstring#includealgorithmusingnamespacestd;constintN105;intn,m,w[N],v[N],dp[1000005];// dp[j]: 获得价值j所需的最小重量intmain(){cinnm;for(inti1;in;i){cinw[i]v[i];// 重量, 价值}memset(dp,0x3f,sizeof(dp));// 初始化为无穷大dp[0]0;// 价值0需要重量0// 0/1背包求获得价值j的最小重量for(inti1;in;i){for(intj1e5;jv[i];j--){dp[j]min(dp[j],dp[j-v[i]]w[i]);}}// 从高到低查找不超过重量限制的最大价值for(intj1e5;j0;j--){if(dp[j]m)// 重量不超过m{coutj;break;}}return0;}【运行结果】3 8 3 30 4 50 5 60 90
题解：学而思编程 超大容量背包
发布时间：2026/6/14 15:47:06
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程超大容量背包【题目描述】有n nn个物品编号从1 11到n nn每个物品有一个重量w i w_iwi和价值v i v_ivi。Taro有一个背包容量为W WW他想要挑选一些物品装到背包里面要求选择的物品重量和不能超过W WW。Taro想知道他能获得的最大价值是多少【输入】第一行两个整数n ( 1 ≤ n ≤ 100 ) n(1≤n≤100)n(1≤n≤100)和W ( 1 ≤ W ≤ 10 9 ) W(1≤W≤10^9)W(1≤W≤109)。接下来n nn行每行两个整数w i ( 1 ≤ w i ≤ W ≤ 10 9 ) w_i(1≤w_i≤W≤10^9)wi(1≤wi≤W≤109)和v i ( 1 ≤ v i ≤ 10 3 ) v_i(1≤v_i≤10^3)vi(1≤vi≤103)表示第i ii个物品的重量和价值。【输出】输出一行包含一个整数表示Taro能获得的最大价值。【输入样例】3 8 3 30 4 50 5 60【输出样例】90【核心思想】问题分析给定n nn个物品重量w i w_iwi价值v i v_ivi和背包容量W WWW ≤ 10 9 W \leq 10^9W≤109求在重量不超过W WW的情况下能获得的最大价值。由于W WW很大10 9 10^9109无法使用常规的以重量为维度的DP。但价值v i ≤ 10 3 v_i \leq 10^3vi≤103且n ≤ 100 n \leq 100n≤100总价值上限为10 5 10^5105可以使用以价值为维度的逆向DP。算法选择逆向DPdp[j]表示获得价值j jj所需的最小重量维度转换将重量限制下的最大价值转化为价值目标下的最小重量关键步骤初始化dp[0] 0获得价值0需要重量0其余为无穷大状态转移逆序遍历价值j jj从v i v_ivi到总价值上限dp[j] min(dp[j], dp[j - v[i]] w[i])选或不选第i ii个物品统计答案从高到低遍历价值j jj找到第一个满足dp[j] W的j jj即为最大价值时间/空间复杂度时间复杂度O ( n × V t o t a l ) O(n \times V_{total})O(n×Vtotal)其中V t o t a l n × max ( v i ) ≤ 10 5 V_{total} n \times \max(v_i) \leq 10^5Vtotaln×max(vi)≤105空间复杂度O ( V t o t a l ) O(V_{total})O(Vtotal)一维数组01背包逆向DP的核心思想维度转换策略当重量范围大、价值范围小时将DP维度从重量转换为价值逆向思维dp[j]表示获得价值j jj所需的最小重量而非传统DP中重量j jj下的最大价值逆序遍历01背包的一维优化需要逆序遍历避免重复选择结果查找从高价值向低价值查找第一个满足重量约束的值即为答案适用于重量范围极大、价值范围较小的背包问题【算法标签】#01背包【代码详解】#includeiostream#includecstring#includealgorithmusingnamespacestd;constintN105;intn,m,w[N],v[N],dp[1000005];// dp[j]: 获得价值j所需的最小重量intmain(){cinnm;for(inti1;in;i){cinw[i]v[i];// 重量, 价值}memset(dp,0x3f,sizeof(dp));// 初始化为无穷大dp[0]0;// 价值0需要重量0// 0/1背包求获得价值j的最小重量for(inti1;in;i){for(intj1e5;jv[i];j--){dp[j]min(dp[j],dp[j-v[i]]w[i]);}}// 从高到低查找不超过重量限制的最大价值for(intj1e5;j0;j--){if(dp[j]m)// 重量不超过m{coutj;break;}}return0;}【运行结果】3 8 3 30 4 50 5 60 90
