关于01背包问题(入门) 笔记
2024-08-10 23:35:26
发布于:广东
01背包问题
目录
1——问题概览
2——DP实现(状态转移方程推论)
3——对于01背包问题的优化 二维到一维
问题概览
难度:普及 题目:YBT1267 01背包问题(模版)
描述:
一个旅行者有一个最多能装公斤的背包,现在有件物品
它们的重量分别是,它们的价值分别为
求旅行者能获得最大总价值。
DP实现(状态转移方程推论)
首先为什么要叫这为01背包问题???
由题可得,对于任一物品只有拿取或者不拿这两种选择(对于一次选择,执行或不执行)
因此也就由"01"代表这个意思了,这是背包问题的root也是最简单的背包问题
如果用普通的搜索来解决,时间复杂度是,这简直惊为天人!!!
思考下,我们可以把问题分阶段为取第件物品且容量为时可获得的最大价值,从第件商品与背包容量为时开始往后递推,找到每一阶段的最大值,最终肯定能找到全局最优解,满足动态规划的最优子结构特点
因为前面物品已经为最优了,所以只需要看放第个物品和不放第i个物品所获的价值哪个大
但放下也有前提条件,就是第个物品重量要小于当前背包容量,不然你就算把背包掏空也塞不下......
简易分析得以下结论
A.放不了:直接不放这个物品,最优解——放这个物品前的最优解
B.放得下:
a.先清空背包,只放这个物品,再看看剩余容量能否装下之前的物品,最优解——这个物品的价值+背包剩余容量的最优解
b.不放这个物品,最优解——放这个物品前的最优解
然后,a、b 情况进行比较,选出真正的最优解
设为当操作物品为个,背包容量为时所获最大价值
状态转移方程就是
注:指第件物品的重量 指第件物品的价值
代码实现如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205][205];//当操作物品数为i,背包容量为v时所获最大价值
ll maxn(ll x,ll y){
if(x>y){return x;}
else{return y;}
}
int main(){
memset(DP,0,sizeof DP);
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i].weight>>a[i].value;
}//输入
for(int i=1;i<=n;i++){//递推每一个物品操作,对于任一物品只有拿或不拿两行为
for(int v=1;v<=m;v++){//递推容量的每一种情况
if(a[i].weight>v){//对于当前物品,超过容量上限,放不下的情况
DP[i][v]=DP[i-1][v];//等于上一个物品操作时所获最大价值,相当于没放
}
else{//如果可以放下
DP[i][v]=maxn( DP[i-1][v] , DP[i-1][v-a[i].weight]+a[i].value );
//考虑不放和放哪一个的价值更大,哪个大存哪个
}
}
}
cout<<DP[n][m];//当n个物品都完成操作,且m的容量都被分配时即为最大
//直接输出DP[n][m]
return 0;
}
对于01背包问题的优化 二维到一维
其实对于01背包的时间已经到了,没法再优化了
但对于空间却可以进一步压缩
我们重新定义为背包容量为下所获的最大价值
根据我们上文的分析
其中和都是上一次操作时,容量为和下所得最大价值
可知每一次的都依赖上一轮的最大值
但是我们可以使用逆推来省去的步骤,因为在一轮之后的轮中存储的都是上一次所能获得的最大值
这就使得代替了的功能,并且压缩了空间
状态转移方程为:
注:为不放时所获的值 为放时所获的值
为什么使用逆推不用顺推??? 初学的本蒟蒻在一开始整理个人笔记时也有该问题...
但是如果你通过YBT原题给出样例去填表发现
顺推下DP表:
0 1 1 2 2 3 3 4 4 5
0 0 3 3 4 6 6 7 9 9
0 0 0 5 5 6 8 10 10 11
0 0 0 0 0 0 9 10 10 12
逆推下DP表:
0 1 1 1 1 1 1 1 1 1
0 0 4 4 4 4 4 4 3 3
0 0 0 9 9 8 8 6 5 5
0 0 0 0 0 0 12 10 9 9
很明显顺推情况下DP表是错误的
因为在顺推情况下会存到同一轮前面的值也就是相当于存了但我们要的是
这样在优化后01背包的空间复杂度为了 优化代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205];//当背包容量为v下所能获最大价值
ll maxn(ll x,ll y){
if(x>y){return x;}
else{return y;}
}
int main(){
memset(DP,0,sizeof DP);
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i].weight>>a[i].value;
}//输入
for(int i=1;i<=n;i++){
for(int v=m;v>=a[i].weight;v--){//逆推
DP[v]=maxn(DP[v-a[i].weight]+a[i].value,DP[v]);
}
}
cout<<DP[m];
return 0;
}
这里空空如也
有帮助,赞一个