01背包问题模板题题解&学习笔记
1 学习笔记
1.1 算法介绍
01背包问题是一种用来计算在一定的空间内能装下的价值最大为多少。有点类似小偷偷东西计算能拿走的最大价值是多少。
1.2 算法流程
$$二维01背包$$
我们可以用$dp_i$$_j$表示前$i$个物品使用$j$的空间所能装的最大价值。
然后考虑状态转移
$dp_i$$_-$$_1$$ _j$ 表示前$i-1$个物体使用$j$的空间可以装的最大价值。
考虑两种情况:
- 不选择当前物品。那么直接就是使用$dp_i$$_-$$_1$$_j$,因为不选当前物体,就相当于前$i-1$个物品所能得到的最大价值,也就是$dp[i-1][j]$
- 选择当前物品。因为我们要选择当前物品,所以我们需要给出这么多空间,所以第二维就是$j-v[i]$ ,由于前$i$个物品需要前$i-1$个物品推出来,所以第一维就是$i-1$,那么要通过前$i-1$个物品加上新选的物品的价值,就是$dp[i-1][j-v[i]]+w[i]$
我们需要将空间每个空间所能获得的最大值都求出来,以便推出新状态,所以结合上述内容,代码就是
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)//m表示背包容积
{
if(j>=v[i]/*v[i]表示第i个物体的体积*/) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]]);//更新,取最优解
}
}
$$01背包一维优化$$
如果我们将代码的第一维省掉,代码会报错中的$dp[i]$就直接表示了前i个物品使用j空间所能保存的最大价值。这时更新状态可以直接覆盖,就相当于选新的物品更新了。
但是要注意,为了避免出现 bellman_ford算法 中连续更新直到终点导致无法准确判断是否用了$k$段(就是说,如果直接像刚才一样从$0 到 m$更新,我们更新了$k$的点,但是如果有一个点$j$需要使用点k更新,那么就直接更新了两遍)
如图:
但是如果$j$是从大到小枚举的话:
所以代码只需要去掉一维,然后改变$j$的枚举顺序就能得出答案。
2.模板题题解
二维01背包:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int c[N],d[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&d[i]);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j-c[i]>=0)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+d[i]);
}
else dp[i][j]=dp[i-1][j];
}
}
int mx=(int)-1e9;
for(int i=0;i<=m;i++) mx=max(dp[n][i],mx);
printf("%d",mx);
}
一维01背包
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
int dp[1010];
int w[N],v[N];
signed main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
printf("%d",dp[m]);
}