动态规划—背包问题

m0_62112384

1649人浏览 · 2024-11-04 19:32:49

m0_62112384 · 2024-11-04 19:32:49 发布

题目一 01背包

图源ACWING

解题思路

二维实现思路：
在这里插入图片描述
简单来说：f[i][j]可以严格拆分成f[i - 1][j]（不含物品i）和f[i - 1][j - v[i]] + w[i]（包含物品i）两种策略，而为了实现价值最大，在这两种策略中取最大值即可。需要注意的是必须要求背包容量j >= 当前物品体积v[i]时后者才有意义；

一维实现思路：

观察到二位实现的代码 f[i] 仅用到了f[i-1]层, i仅仅代表了不同层级，因此可以优化
j与j-v[i] 均小于j ， j可以不从0开始循环，范围应在(v[i] 到最大背包体积)
若用到上一层的状态时,从大到小枚举, 反之从小到大

具体优化步骤

观察到二位实现的代码 f[i] 仅用到了f[i-1]层, i仅仅代表了不同层级，因此可以优化

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j <= m; j ++ )
        {
            if (j >= v[i])
            {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }
            else
            {
                f[i][j] = f[i - 1][j];
            }
        }
    }

可以优化成

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j <= m; j ++ )
        {
            if (j >= v[i])
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
            else
            {
                f[j] = f[j];//优化后发现无意义可以进一步直接删除此步骤
            }
        }
    }

j与j-v[i] 均小于j ， j可以不从0开始循环，范围应在(v[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]);
        }
    }

为什么j是从大到小而不是从小到大？:

        for (int j = v[i]; j <= m; j ++ )
        {
        	f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

其实等同于未修改前的

f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);//等同于f[j]由当前层的f算出，
//因为j从小到大遍历，f[j - v[i]]实际上已经被计算过

并没有体现源代码中的f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);第i层f是由上一层的f计算出的

综上，必须让j从大到小遍历，才能在更新f[j]时用上一层的f计算（此时上一层的f未被跟新过）

代码实现

二维实现：

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;

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

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

一维实现：

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;

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

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

题目二完全背包

图源ACWING

解题思路

朴素做法（三重循环）

可以将问题分割成：

不拿第i件物品
拿第i件物品：包括拿1件，2件，3件…k件物品i

可以得出递推式:f[i][j] = max (f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i]);
k代表拿k件物品i

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N];

int main()
{
    int n, m;
    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 = 0; 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];
    return 0;
}

二维优化（二重循环）

注意到：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w,…)
f[i][j - v] = max (f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, …)
所以f[i][j] = max(f[i - 1][j], f[i][j - v] + w)

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N];

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

一维优化

思路与01背包的一维优化类似

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];

int main()
{
    int n, m;
    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];
    return 0;
}

注：
完全背包中，j是从v[i]到m，从小到大遍历的
01背包中，j是从m到v[i],从大到小遍历的

因为在完全背包中f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);用的是同一层的f[i]，意味着f[i][j - v[i]]已经计算过；
而在01背包中f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);用的是不同层，意味着f[i - 1][j - v[i]] + w[i]未被计算；

题目三多重背包

图源ACWING

解题思路

朴素做法（三重循环）

只在上述完全背包的循环中加上物品数量的判断

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 110;
int f[N][N], v[N], w[N], s[N];

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

时间复杂度为1000 * 2000 * 2000 = 4e9 会超时

二进制优化

在这里插入图片描述
原链接：https://www.acwing.com/solution/content/20115/

代码实现

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

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; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s; 
            w[cnt] = b * s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    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;
}

为什么不能用完全背包的优化方法优化多重背包？
：完全背包中的物品数量没有限制，可以无限取则有
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w,…, f[i - 1][j - sv] + sw)
f[i][j - v] = max (f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, …, f[i - 1][j - sv] + (s - 1)w)
所以f[i][j] = max(f[i - 1][j], f[i][j - v] + w)

在多重背包中，物品的数量是有限制的，无法无限取得，意味着能取的物品的数量受到背包容量和物品数量的双重限制，则有：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w,…, f[i - 1][j - sv] + sw)
f[i][j - v] = max (f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, …, f[i - 1][j - sv] + (s - 1)w, f[i - 1][j - (s + 1)v] + sw);
所以f[i][j] ≠ max(f[i - 1][j], f[i][j - v] + w)

题目三分组背包问题

图源ACWING

解题思路

朴素做法（二维）

该题状态计算可以表示为：

不选第i组内的任何物品
选第i组内的第j个物品

则有：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][j]] + w[i][j])

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N], f[N][N];

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

PS：为什么不能写成

       for(int j = 0; j <= m; j ++){                                        
           for(int k = 1; k <= S[i]; k ++)
               if(j >= v[i][k])
                   f[i][j] = max(f[i-1][j] , f[i-1][j - v[i][k]] + w[i][k]);
				else
					f[i][j] = f[i - 1][j];        
        }

因为如果f[i][j] = max( f[i-1][j] , f[i-1][ j - v[i][k] ] + w[i][k]] ，假设f[i-1][j] = 1, f[i-1][ j - v[i][k] ] + w [i][k] 由于有改组一共有三个物品，故一共有三个值，分别是5， 6， 4；当在for循环里进行比较时， f [ i ] [j ] = max( 1, 6) ; f[i][j] = max( 1, 5) ; f[i][j] = max(1, 4) 最后一层循环过完，结果f[i][j] = 4; 而本应该是 1 , 6, 5, 4 中取最大值6

优化做法（一维）

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N], f[N];

int main()
{
    int n, m;
    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 -- )//不知道第i组内体积最小物品，所以必须从m遍历到0；
        //同时由于用的是不同层的f来进行的状态转移，必须从大到小遍历
        {
            for (int k = 1; k <= s[i]; k ++ )
            {
                if (j >= v[i][k])
                {
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);    
                }
            }
        }
    }
    
    cout << f[m];
    return 0;
}

总结

若是状态转移方程中有意义的参数用的是不同层级的函数，则优化时体积必须从大到小遍历。
例如：f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);max第二个参数就用到了不同层的函数，一维优化时体积必须从大到小遍历
若是状态转移方程有意义的参数用的是同一层的函数，则优化时体积必须从小到大遍历。
例如：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);max第二个参数用的是本层的函数，一维优化时体积必须从小到大遍历
（为什么f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])第一个参数无意义？因为一维优化后就变成了f[j] = max(f[j], f[j - v[i]] + w[i])）
要着重考虑状态计算的过程能划分为几个方案，有了状态计算的方案才能写出代码