当前位置：首页 > article >正文

算法学习系列（三十二）：背包问题

article 2024/11/15 15:27:55

引言

从这一篇文章开始，就开始学习动态规划了，也就是DP了，然后就是DP可以说是整个算法中的最难学的部分之一，好写是非常的好写的，每道题也只有很短的代码量，但是主要是它这个动归方程不好想，也不好推导出来，而且这类题都没有一个好的模板，只能说都是通过大量的做题凭经验得出来的，所以说得好好做题，好好思考，话不多说，那就开始吧。

一、01背包

问题：每件物品有各自的重量和价值，从n件物品中任选多个，重量不能超过m，每件物品只能选一次，求能选出物品的最大价值

1.二维代码模板

思想：第 $i$ 件物品，要么拿要么不拿，如果不拿那就是 $f [i - 1] [j]$ ，如果拿，那么最大值为 $f [i] [j] = f [i - 1] [j - v [i]] + w [i]$ ，也就是先找把第i个物品去除的最大值，再加上这个物品就是拿的最大值。

const int N = 1010;

int n, m;
int v[N], w[N];  // 第i件物品的体积，价值（权重）
int f[N][N];

int main()
{
    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 = 1; j <= m; ++j)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

2.一维代码模板

优化对代码或方程进行等价变形

思路：首先 $f [i] [j]$ 中用的都是 $i - 1$ ，而没有用到 $i - 2, i - 3...$ ，所以就可以用滚动数组来，就可以去掉一维。然后对方程进行等价变形，之后由于 $j$ 是从 $v [i]$ 到 $m$ ，由小到大变的，所以再计算 $f [j - v [i]]$ 时，由于 $j - v [i] <= j$ ，所以 $f [j - v [i]]$ 计算的是第 $i$ 层的已经被算过了，而应该算的是 $i - 1$ 层的，所以 $j$ 改为由大到小遍历，这样 $f [j - v [i]]$ 在遍历时就是第i-1层的了，这样就对了

const int N = 1010;

int n, m;
int v[N], w[N];  
int f[N];

int main()
{
    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 >= v[i]; --j)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

二、完全背包

问题：每个物品可以选无数个，其余跟01背包是一样的

1.朴素代码模板

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][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 = 1; j <= m; ++j)
        {
            for(int k = 0; k * v[i] <= j; ++k)
            {
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

2.二维优化代码模板

核心：在k次循环里 $f [i] [j] = f [i] [j - v [i]] + w [i]$

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][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 = 1; j <= m; ++j)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

3.一维代码模板

思路:降维的过程，跟01背包是一样的，然后由于这个所优化后的 $f [j - v [i]]$ 就是第i层的，所以 $j$ 从小到大遍历就是正确的。
然后这个代码发现跟01背包基本是一样的，只不过 $j$ 是01背包是从大到小，完全背包是从小到大。

const int N = 1010;

int n, m;
int v[N], w[N];
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 = v[i]; j <= m; ++j)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

三、多重背包

问题：每件物品有 $s [i]$ 个，其余跟完全背包一样

1.朴素做法

思想：跟完全背包一样，只不过k限制个数

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            for(int k = 0; v[i] * k <= j && k <= s[i]; ++k)
            {
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);  //一个都不选，选k个
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

2.优化版本

思想：就是把这个背包变成01背包，第 $i$ 件物品选 $k$ 件，把这 $k$ 件物品当成一个物品，k以 $2$ 次幂增长，最后01背包选的时候可以通过选多个物品可以凑出 $2^k$ 种可能的结果。然后每个物品依次这样，体积和权重就是单个乘以选的总数，最后再用01背包解决就行了，相当于把所有种组合罗列出来，算最优解。

const int N = 25000, M = 2010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    int cnt = 0;
    for(int i = 1; i <= n; ++i) 
    {
        int a, b, s;
        cin >> a >> b >> s;
        
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k <<= 1;  //每件物品背包里会有k^2个，然后可以凑出任意一种情况
        }
        if(s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = m; j >= v[i]; --j)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

四、分组背包

问题：有多个背包，每个背包中最多只能选一件物品，在规定的体积中，选出最大价值

1.朴素做法

思想：其实就是多个01背包，每个背包中要么不选，要么选一个

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; ++j) cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            f[i][j] = f[i-1][j];  //不选
            for(int k = 1; k <= s[i]; ++k)
            {
                if(v[i][k] <= j) f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]);  //选第k个
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

2.一维优化

思想：跟之前讲的优化一样

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; ++j) cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; ++i)
    {
        for(int j = m; j > 0; --j)
        {
            for(int k = 1; k <= s[i]; ++k)
            {
                if(v[i][k] <= j) f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}