01背包问题
题目 01背包问题
思路分析
有了前两道题的引入 现在尝试一下01背包
拿到这个问题的时候先会有一种想法：
把每个物品排一下序
因为有个体积v还有个价值w 那把w/v就是性价比
把它排个序 然后用类似贪心的思想去写（每次选性价比最高的）
咋一看很有道理
但其实是不对的
比如 n=2 v=5
（1）v=5 w=5 性价比:1
（2）v=3 w=4 性价比：4/3 貌似（2）的性价比更高 但实际答案应该是（1）
这其实就是一个全局最优和局部最优的问题
（很欣慰的是前面刚悟到了Dijkstra贪心局部最优和spfa的考虑dp全局最优的区别 在这里又印证了 不禁感慨 y总真的是tql）
对于这种考虑大局的问题 要使用dp去写 用贪心的话就显得目光短浅了
不扯了 先分析这题
老规矩 还是先暴力去写 然后想办法改成dp
暴搜：
不外乎就是对于每个物品 有选和不选两种方案
与前面不同的是 此时的节点存放的是背包剩余体积和价值
而边表示对于每个物品选与不选（往左不选往右选）
然后孩子结点就是执行选或不选操作后 背包的新状态 那么显而易见 使用dfs可以得到所有答案 其中就可以得到最优解
从第一个物品开始选 初始的剩余空间spv为m
对于每个物品有选和不选两种方案
当背包剩余空间不够时（spv<v[x]）只能不选
当背包剩余空间够时（spv≥v[x]） 就有待考量 取的是选与不选的价值的最大值
思路是没问题的 但是只能过6个数据（一半）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int dfs(int x,int spV)
{
if(x>n)
return 0;
//容量不够放下该物品时 只能跳过该物品继续往后走
else if(spV<v[x])
return dfs(x+1,spV);
//容量够时 可以放也可以不放 两种选择 保留最后最大的
else if(spV>=v[x])
//如果放了 容积就会减小 且背包内价值会增大
return max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
那么 加上记忆化搜索试试
可以通过
运行时间： 121 ms
运行空间： 4188 KB
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int mem[N][N];//记忆化数组(两个参数所以二维)
int dfs(int x,int spV)
{
if(mem[x][spV])
return mem[x][spV];
int sum=0;
if(x>n)
sum = 0;
else if(spV<v[x])
sum = dfs(x+1,spV);
else if(spV>=v[x])
sum = max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
mem[x][spV]=sum;
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
再然后就是改成dp
根据递归搜索树分析 也是可以从大推到1 得出答案
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//递归搜索树里树叶是较大 树根是较小 所以n~1往前推
for(int i=n;i>=1;i--)
{
//遍历体积
for(int j=0;j<=m;j++)
{
if(j<v[i])//如果放不下 直接等于之前的状态
{
f[i][j]=f[i+1][j];
}
if(j>=v[i])//如果放得下 就要取选或不选 结果更大的那种
{
f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
}
}
}
cout<<f[1][m];
return 0;
}
可以发现 dp就是对dfs的优化
减去了递的过程 将递归变成了循环 并利用数组存储算过的值 实现记忆化
从顶开始 动态地记录答案 剪枝 ————动态规划！
那么后续的问题应该就是 我总不能对每道题都写三个解法然后得到dp吧
知道了dp是怎么回事后 就该使用dp的思维去思考问题了
核心不外乎就在于状态表示和状态转移
f[i][j]即状态 其实就代表着某个节点 要清楚他的含义 ij代表什么 fij又代表什么 以及存的是什么max还是总和
然后就是状态转移 我怎么从子问题中计算得到这个节点的状态（从孩子往上推 把已知的孩子的状态转移成当前点的状态）
再用前面的例子来看
楼梯问题：识别子问题 - 每个台阶有多少种上法。构建状态 - 第 i 级台阶的方案数。状态转移 - 第 i 级台阶的方案数等于第 i-1 级和第 i-2 级的方案数之和为。
小偷问题：识别子问题 - 在不触动警报的情况下，从前 i 间房子中可以偷窃a的最高金额。构建状态 - 最高金额。状态转移 - 第 i 间房的状态取决于偷或不偷第 i 间房，即 max(前一间房的金额, 前两间房的金额 + 当前房间的金额)。
01背包问题：识别子问题 - 在特定容量下的最大价值。构建状态 - 不同容量下的最大价值。状态转移 - 每个物品决定是否放入背包，即 max(不放入当前物品的价值, 放入当前物品后的总价值)。
首先要思考的是如何将问题分解成可以通过之前计算的结果来解决的子问题，然后构建状态和状态转移方程。这种自底向上的思维方式是DP的核心。
根据现在的思路和y总思路的对比
方向不太一样 但道理一样
现在还停留在从底往上 即把二叉树构造完后 再从叶节点往上走
比如对于某个点选不选 得从左孩子和右孩子两遍考虑
不选其实就是左孩子的值保留一下 什么都不用变
选的话 就是把右孩子的值减去一定容量v 然后再加上一定价值w
而y总是从上往下分析
如果该点不选 就是i-1,j
如果该点选 就是但是不好算出到i的状态 所以同时减去该点 形成i-1,j-v +w
本质得到的公式是一样的 但从底而上就需要绕很多弯
要学会这种从顶而下的思路 把一个问题分解成子问题 这才是真正的dp
闫氏dp分析法！
集合角度考虑问题
核心不变 分析变成了从上而下 把下当已知 从上而下的话就会有一个问题 若包含该物品 不太好算 得进行一下”曲线救国”先把第i个物品去掉 空出第i个物品的体积 再在不包含i物品的j-v[i]的情况下 加上第i个物品的权重 （实质是和dfs里分析的一样 不过现在从上往下想 要绕个弯）
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//第0个物品无需考虑 f[0][0~m]的最大价值永远是0 初始化成0（全局）
//从第1个物品开始考虑
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//还是一样的 左边的集合是一定存在的（不选）
//右边的集合有可能是空集 （剩余体积不够时）
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
接下来再考虑空间上的优化
分析状态转移方程
注意点就是 看要用的数据是本层的还是上层的 决定是从大到小变量还是从小到大（覆盖前用或是覆盖后用） 不要错用数据
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
//因为 j-v[i]<j 如果从小到大枚举的话 用的就是已经覆盖了的第i层的f[j-v[i]]
//而我们要的是 第i-1层的f[j-v[i]] 所以得在覆盖前就算出来 所以把遍历顺序改成从大到小
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}
之后想问题就是这样 画图 以集合分析 状态表示 状态计算 在写出朴素做法后 再考虑如何优化
代码实现
dfs
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int dfs(int x,int spV)
{
if(x>n)
return 0;
//容量不够放下该物品时 只能跳过该物品继续往后走
else if(spV<v[x])
return dfs(x+1,spV);
//容量够时 可以放也可以不放 两种选择 保留最后最大的
else if(spV>=v[x])
//如果放了 容积就会减小 且背包内价值会增大
return max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int mem[N][N];//记忆化数组(两个参数所以二维)
int dfs(int x,int spV)
{
if(mem[x][spV])
return mem[x][spV];
int sum=0;
if(x>n)
sum = 0;
else if(spV<v[x])
sum = dfs(x+1,spV);
else if(spV>=v[x])
sum = max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
mem[x][spV]=sum;
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}
dfs改dp
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//递归搜索树里树叶是较大 树根是较小 所以n~1往前推
for(int i=n;i>=1;i--)
{
//遍历体积
for(int j=0;j<=m;j++)
{
if(j<v[i])//如果放不下 直接等于之前的状态
{
f[i][j]=f[i+1][j];
}
if(j>=v[i])//如果放得下 就要取选或不选 结果更大的那种
{
f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
}
}
}
cout<<f[1][m];
return 0;
}
闫氏dp分析法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//第0个物品无需考虑 f[0][0~m]的最大价值永远是0 初始化成0（全局）
//从第1个物品开始考虑
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//还是一样的 左边的集合是一定存在的（不选）
//右边的集合有可能是空集 （剩余体积不够时）
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
//f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);(前面有 f[i][j]=f[i-1][j];)
}
}
cout<<f[n][m];
return 0;
}
滚动优化
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
//因为 j-v[i]<j 如果从小到大枚举的话 用的就是已经覆盖了的第i层的f[j-v[i]]
//而我们要的是 第i-1层的f[j-v[i]] 所以得在覆盖前就算出来 所以把遍历顺序改成从大到小
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}
💬 评论