背包九讲

MoCaRabbit · 2023-07-11 17:42:16 · 个人记录

01背包

例题:采药.

我们可以用搜索完成,\text O(2^n)，会T的飞起.

搜索中，一般会带进这些参数: 正在选的数与已选数的背包容积。

我们可以对其记忆化，其时间复杂度达到 O(nm)，够快了。

我们继续把它用递推形式写下来。

因为递推习惯从小向大递推状态，所以改一个顺序递推，得到以下代码:

#include<bits/stdc++.h>
using namespace std;
int t,m;
int dp[110][1010],t1[1010],m1[110];
int main() {
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&t1[i],&m1[i]);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){
            dp[i][j]=(j>=t1[i] ? max(dp[i-1][j],dp[i-1][j-t1[i]]+m1[i]) : dp[i-1][j]);
        }
    }
    cout<<dp[m][t];
    return 0;
}

背包问题算一种动态规划（dp）,所以数组叫 dp.

但这样，我们就罢休了吗？

不，因为 dp[i][x] 只用到了 dp[i-1] 层的东西，所以我们只需要记录 dp[i-1] 层的数组。

这个叫做滚动数组优化。

因为递推是从下自上推的，所以为了满足 二维数组的递推式，我们写内层循环时需要从大到小枚举。

代码:

#include<bits/stdc++.h>
using namespace std;
int t,m;
int dp[1010],t1[1010],m1[110];
int main() {
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&t1[i],&m1[i]);
    }
    for(int i=1;i<=m;i++)
        for(int j=t;j>=t1[i];j--)
            dp[j]=max(dp[j],dp[j-t1[i]]+m1[i]);
    cout<<dp[t];
    return 0;
}

完全背包

例题:疯狂的采药.

此题当然可以三层循环高时间复杂度枚举 + 滚动数组优化。

当然，这过不了。

要想过此题，需要用 \text O(mt) 的时间复杂度。

我们其实可以将 01背包 的倒序循环改成正序就行了。

因为 01背包 的倒序循环是为了防止重复选择，但是 完全背包 又 允许重复，所以可以这样做。

代码:

#include<bits/stdc++.h>
using namespace std;
long long dp[int(1e7)+10];
int m,t;
long long w[int(1e4)+10],v[int(1e4)+10];
int main() {
    cin>>t>>m;
    for(int i=1;i<=m;i++)
        cin>>w[i]>>v[i]; 
    for(int i=1;i<=m;i++)
        for(int j=w[i];j<=t;j++)
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
    cout<<dp[t];
    return 0;
} 

多重背包

例题:宝物筛选

此题的背包有个特点，每个物品虽然可以重复选择，但是每个物品选择的数是有限的。

此题可以将它拆成 01 背包求解。

通过三层循环，列出状态转移方程 dp_{i,j}=\min(dp_{i-1,j},dp_{i-1,j-k \times w_i}+k \times v_i)。