dp背包

(这篇题解可能和别的题解不同,一共有两个完整的AC代码) 解题思路 很典型的01背包问题 可以选择二维dp或者一维dp 二维DP思路: 1. 遍历每一个状态 2. 根据前一个状态，选择装或者不装之间的较大值 3. 取最末状态，最大容量为答案 AC代码 二维DP代码 > 执行用时 8ms > 内存消耗 0.97MB 一维DP代码 > 执行用时 5ms > 内存消耗 0.59MB 欢迎加入团队 制作题解不易,跪求点赞!!!

模板题，没什么好说的

深度优先搜索

点赞

dp模板啊

本蒟蒻第n次写题解 一维dp： 二维的： 其实题目很简单，像我一样的蒟蒻都能做

经典01背包 .cpp #include<iostream> using namespace std; int t,n,a[110],b[110],dp[110][100010]; int main() { scanf("%d%d",&t,&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); for(int i=1;i<=n;i++) for(int j=1;j<=t;j++) { if(j>=a[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]); else dp[i][j]=dp[i-1][j]; } printf("%d",dp[n][t]); return 0; }

二维dp： 一维：

由于 dp⁡(i,j)\operatorname{dp}(i,j)dp(i,j) 的值仅取决于上一层 dp⁡(i−1,...)\operatorname{dp}(i-1,...)dp(i−1,...)的值，故我们可以尝试将dp转化为一维的。 以下是代码：

昨天学了下背包，cpu都要烧干了，写了1上午了

经典01背包

01背包，以下是2维dp代码

一、题目分析 1. 题意转化为经典背包模型 * 总采药时间 T → 背包最大容量 * 草药数量 M → 物品个数 * 每株草药采摘耗时 w[i] → 物品重量 * 每株草药价值 v[i] → 物品价值 * 限制：每株草药只能采一次（01背包，每件物品只能选/不选二选一） * 目标：总耗时不超过 T，采到草药总价值最大 2. 输入输出样例拆解 输入： 可选组合：草药2+草药3，总耗时 69+1=70，总价值 1+2=3，对应输出3。 二、动态规划核心思路（二维DP） 1. 状态定义 dp[i][j]：只考虑前i株草药，总采摘时间不超过j时，能获得的最大总价值 * 第一维i：草药编号（0~M，i=0代表一株草药都不选） * 第二维j：可用总时间（0~T，j=0代表没有时间，价值必为0） 2. 初始化规则 全局数组默认初始值全为0，天然满足边界条件： 1. dp[0][j] = 0：一株草药都不采，无论多少时间，价值都是0 2. dp[i][0] = 0：没有任何可用时间，什么草药都采不了，价值0 3. 状态转移方程（核心） 遍历每一株草药i，再遍历所有可用时间j，分两种情况： 情况1：当前草药耗时 > 当前可用时间（W[I] > J） 时间不够，不能采第i株草药，最优解和只考虑前i-1株完全一样： dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j] dp[i][j]=dp[i−1][j] 情况2：当前草药耗时 ≤ 当前可用时间（W[I] ≤ J） 有两种选择，取价值更大的一种： 1. 不采第i株：价值 = dp[i-1][j] 2. 采第i株：先预留出采它的时间w[i]，剩下j-w[i]时间在前i-1株里选最优，再加上当前草药价值：dp[i-1][j-w[i]] + v[i] dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) 4. 最终答案 dp[M][T]：全部M株草药都考虑，总时间上限T，最大价值。 三、逐行代码详解 四、样例模拟推演（直观理解DP表格） 样例参数：t=70，m=3 草药1：w=71,v=100；草药2：w=69,v=1；草药3：w=1,v=2 1. i=1（处理第一株，耗时71） 所有j≤70都满足71>j，所以整行dp[1][j] = dp[0][j] = 0，第一行全0。 2. i=2（处理第二株，耗时69，价值1） * j < 69：时间不足，dp[2][j]=0 * j ≥ 69：可以采草药2，dp[2][j] = max(0, dp[1][j-69]+1) = 1 即j=69~70时，值为1。 3. i=3（处理第三株，耗时1，价值2） 逐个j计算，重点看j=70： * 不采草药3：dp[2][70]=1 * 采草药3：dp[2][70-1] + 2 = dp[2][69] + 2 = 1 + 2 = 3 取最大值3，最终dp[3][70]=3，和样例输出一致。 五、复杂度分析 * 时间复杂度：O(M×T)O(M \times T)O(M×T) 外层循环M次，内层循环T次，本题M≤100，T≤1000，总运算量仅1e5，完全无压力。 * 空间复杂度：O(M×T)O(M \times T)O(M×T) 二维数组105×1005，空间开销很小；进阶可使用一维滚动数组优化到O(T)O(T)O(T)。 六、易错点总结 1. 草药下标从1开始：避免j-w[i]出现负数，简化边界判断； 2. 内层循环j从小到大：二维DP无需倒序；一维01背包才需要倒序遍历容量； 3. 区分01背包和完全背包：本题每株草药只能采一次，不能重复选取； 4. 不要输出dp[m][t]以外的值，必须同时包含全部草药和全部可用时间。 七、拓展：一维空间优化版（可选拓展） 二维数组会重复使用上一层数据，可以压缩成一维数组，只用dp[j]：

题目意思 你有一个容量为 TTT 的背包，而你面前有 MMM 个物品，每个物品都有它的价值和重量。 现在你要让这个背包里装的物品总价值最高，那么这个总价值是多少？ DP 讲解 这道题是 DP（动态规划）的模版题，所以我会详细讲解 DP 的解题过程，会背包 DP 的人可以直接拉到下面看代码。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 对于这类总价值最高的问题，我们可以使用 背包 DP 来解决。 首先我们需要将输入存起来。 使用 viv_ivi 表示一个物品的价值，wiw_iwi 表示一个物品的重量。 接下来维护一个 dpdpdp 数组。 dpidp_idpi 表示的是：当背包容量为 iii 时，最多可以装的总价值。 然后，我们需要枚举每件物品，然后考虑：拿或不拿，谁的价值更高？ 接下来，我们需要枚举背包容量。 需要注意的是，枚举背包容量时，枚举范围是 T 到 w[i] 。 这是为什么呢？ 我们设想一下：如果正序枚举，会发生什么？ 此时，前面枚举的结果会污染到后面的计算，误以为新的计算结果是上一轮的计算结果，从而导致结果偏差。 现在到了最核心的部分：怎么考虑拿不拿谁的价值更高？ 我们可以使用 max() 函数计算，一边是不拿的结果，一边是拿的结果。 左边的值肯定就是 dpjdp_jdpj 了。 而右边的，就是 dp[ j-w[i] ] + v[i] 了。 仔细想一下这个式子，它的意思就是： 所以，核心部分就出来了： 需要注意的地方 * dpdpdp 数组的大小不是 MMM（物品数量），而是 TTT（背包容量）。 * 内层循环的边界是 wiw_iwi ，防止越界 AC CODE

#include<bits/stdc++.h> using namespace std; int main(){ int C,N; cin>>C>>N; int w[100005],v[100005],dp[1005][1005]; for(int i=1;i<=C;i++){ cin>>w[i]>>v[i]; } for(int i=1;i<=N;i++){ for(int j=0;j<=C;j++){ if(j<w[i]){ dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } } cout<<dp[N][C]; return 0; }