动态规划之背包模型及其扩展应用

2023-09-28 09:36:04

背包模型

前言

对于原始背包问题及其优化可以参见这篇博客
背包问题

背包问题的初始化问题

一般问题有以下三种情况
动态规划之背包模型及其扩展应用
对应的初始化方法
动态规划之背包模型及其扩展应用

  1. 对于体积最多是j， f [ 0 ] [ j ] f[0][j] f[0][j]表示一个物品都不选体积最多是j的情况，这个是存在的，所以置为0 ，对于循环中我们是最多是j，如果 v < 0 ,说明 v1 > j ，这是不存在的。
  2. 对于体积恰好是j， f [ 0 ] [ j ] f[0][j] f[0][j]表示一个物品都不选体积最多是j的情况，只有 f [ 0 ] [ 0 ] f[0][0] f[0][0]是存在的，其余的都是这个是不存在的，因此设置为一个不合法的数，至于是正无穷还是负无穷，取决于题目是求最大还是最小；对于循环边界理由和上面一样
  3. 对于初始化条件与第2个一样 ；对于循环条件，我们·是至少是j因此当v<0的时候是存在的，而它们的值是 v = 0 时候的值。

01背包

装箱问题

题目转送门

个人解题思路：

这题是让我们尽可能的让背包的剩余空间小，也就是放入的物品的体积要尽可能的大，因为物品只给了体积没有价值，那么我们就可能将每一个物品的价值等同于它的体积，那么这就转变为了01背包问题。那么这个 d p [ i ] dp[i] dp[i]表示总体积不超过背包容量下的最大体积，也就说剩余体积最小。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 35 , M = 20010;
int n , m ;
int w[N] , v[N] ,f[M];

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

宠物小精灵之收服

题目转送门

解题思路：

这题由单一花费变成了二维花费，我们的花费有精灵球的数量和体力，因此我们定义的是二维dp； d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示考虑前i个精灵，精灵球数量不超过j，体力不超过k的最大的精灵球数量。由背包问题我们可以将第一维的空间省略掉，采用逆序的遍历方式。对于二维我们还是有
动态规划之背包模型及其扩展应用

对于剩余的体力，我们在 f [ N ] [ 1 − M ] f[N][1-M] f[N][1−M]中选出等于 f [ N ] [ M ] f[N][M] f[N][M]的最小的体力，这是花费的最小体力。同时因为体力不能会0，我们再减1.

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110 , M = 1010;
int n , m , K;
int w[N] , v[N] ,f[M][M] ;

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

数字组合

题目转送门

解题思路;

这是一个典型的0/1背包模型，N个正整数就是N个物品，M就是背包的容积。在外层循环到i时(表示从前i个数中选)，设F[j]表示“和为j”有多少种方案。在具体实现中，只需要把原始代码中求max的函数改为求和即可。
代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110 , M = 10010;
int n , m ;
int w[N] , f[M];

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

开心的金明

题目转送门

解题思路:

这题我们可以将每一个物品的钱看成是体积，而物品的价值则是金额*重要程度。这样我们就转化成了01背包问题了、

代码;

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50010;
int n , m;
int f[N];

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

01背包+贪心

题目转送门

解题思路：
动态规划之背包模型及其扩展应用
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10010;
int n , m ;
int f[N];
struct Stone{
    int s , e ,l;
    bool operator < (const Stone & w)const {
        return s * w.l < w.s * l;
    }
}stone[N];

int main(){
    int T;
    cin>>T;
    for(int C = 1 ; C <= T ; ++C){
        m = 0;
        cin>>n;
        for(int i = 0 ; i < n ; ++i){
            int s ,e ,l;
            cin >>s>>e>>l;
            stone[i] = {s ,e,l};
            m += s;
        }
        sort(stone , stone + n);
        memset(f , -0x3f , sizeof f);
        f[0] = 0;
        for(int i = 0 ; i < n ; ++i){
            int s = stone[i].s , e = stone[i].e , l = stone[i].l;
            for(int j = m ; j >= s ; --j)
                f[j] = max(f[j] , f[j-s] + e - (j - s)*l);
        }
        int res = 0;
        for(int i = 0 ; i <= m ; ++i)res = max(res , f[i]);
        cout<<"Case #"<<C<<": "<<res<<endl;
    }
    
    return 0;
}

背包问题求解方案数

货币系统

题目转送门

解题思路·:

这题和上面的数字组合不同的地方在于数字组合是每一个数字只能选一次，而在这里每一个货币可以选多次，因此这就是一个完全背包的模板题，在具体实现中，只需要把原始代码中求max的函数改为求和即可。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 20 , M = 3010;
int n , m;
int w[N] ;
LL f[M];

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

货币系统Ⅱ

题目转送门

解题思路;

等价类有以下三种性质，
动态规划之背包模型及其扩展应用
因此我们要考虑的是对于每一个a[i]查询其是否会被a中其他不含它的数组成，如果不可以我们就要选它，如果可以就不选。那么如何知道呢？那这就是一个和上一题一样的问题了，我们处理完后，对于每一个a[i]如果其 f [ a [ i ] ] ! = 1 f[a[i]]!=1 f[a[i]]!=1那么说明这个数不能由别的数组成

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110 , M = 25010;
int n , m ;
int f[M] , w[N];

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        memset(f , 0 , sizeof f);
        f[0] = 1;
        for(int i = 1 ;i <= n ; ++i){
            cin>>w[i];
            for(int j = w[i] ; j <= M ; ++j)
                f[j] += f[j-w[i]];
        }
        int cnt = 0;
        for(int i = 1; i <= n ;++i)
            if(f[w[i]] == 1)cnt++;
            
        cout<<cnt<<endl;
    }
    
    return 0;
}

多重背包问题

庆功会

题目转送门

解题思路：

我们把拨款金额看成背包容积，价格看成物品体积，价值看成物品价值，那么这个题目就是一个多重背包的裸题。对于这个数据范围我们可以使用二进制优化的多重背包来求解。

多重背包详细解释

代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 510 , M = 6010;
int n , m;
int f[M];
struct Good{
    int w , v;
};
vector<Good>goods;

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

混合背包问题

题目转送门

解题思路：

我们回顾背包问题的表达式： d p [ i ] [ j ] dp[i][j] dp[i][j]表示对于前i个物品，总体积不超过j的最大价值。我们发现它对于物品的类型是没有限定的。不同类型的物品，我们只是在状态计算的时候是不一样的。同时对于第i个物品我们当前只会考虑第i个物品而不用考虑前i-1个物品的情况。因此这题我们对于第i个物品，按照其类型来进行对应的状态计算。

动态规划之背包模型及其扩展应用

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n , m;
int f[N];

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

二维费用的背包问题

二维费用的背包问题

题目转送门

解题分析：
动态规划之背包模型及其扩展应用

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010 ;
int n,m,V;
int f[N][N];

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

潜水员

题目转送门

解题思路：
动态规划之背包模型及其扩展应用

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100;
int n,m , k;
int f[N][N];

int main(){
    cin>>n>>m>>k;
    memset(f , 0x3f , sizeof f);
    f[0][0] = 0;
    for(int i = 1 ; i <= k ; ++i){
        int w1 ,w2 ,c;
        cin>>w1>>w2>>c;
        for(int j = n ; j >= 0 ; --j)
            for(int k = m ; k >= 0 ; --k)
                    f[j][k] = min(f[j][k] ,f[max(0,j-w1)][max(0,k-w2)] + c);
    }
    cout<<f[n][m]<<endl;
    return 0;
}

分组背包问题

分组背包

对于分组背包，每一组的物品可以选与不选，如果选，一组物品中只能选一个。那么到这里我们可以知道在每一组内部的选法类似于01背包，那么我们有如下分析

动态规划之背包模型及其扩展应用

动态规划之背包模型及其扩展应用

for(int i=1;i<=n;i++)
	 for(int j=0;j<=m;j++)
	  for(int k=1;k<=s[i];k++)//s[i]表示第i组物品的个数
	   if(j>=v[i][k])//剩余的背包容量j大于第i组的第k个物品的体积 
	   {
	   	  f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
	   }

机器分配（每一组只取一个）

机器分配

解题思路：
我们将问题抽象一下，将公司看成是一组物品，公司中的物品数量为m，每一个物品体积为j j ， 价值为g[i][j] 。对于方案我们逆序遍历每一组，对于每一组我们依据dp计算式子来找到对应的数量。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 155;
int n ,m;
int f[N][N] , g[N][N];
int ans[N];
int main(){
    cin>>n>>m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j)cin>>g[i][j];
    for(int i = 1 ; i <= n ; ++i) // 组数
        for(int j = 1; j <= m ; ++j) // 体积 
            for(int k = 0 ; k <= j ; ++k) // 决策 ， 可以从0开始表示一个都不选
                f[i][j] = max(f[i][j] ,f[i-1][j- k] + g[i][k]);

    cout<<f[n][m]<<endl;
    
    int   res = f[n][m] , s = m ; // s是当前剩余的总可以体积
    for(int i = n ; i >= 1 ; --i)
        for(int k = 0 ; k <= s ; ++k)
            if(res == f[i-1][s-k] + g[i][k]){
                ans[i] = k;
                s -= k; //体积减少
                res -= g[i][k]; // 价值减少
                break;
            }
    for(int i = 1 ; i <= n ;++i)cout<<i<<" "<<ans[i]<<endl;
    return 0;
}

金明的预算方案（每一组里能取多个）

题目转送门

解题思路：

对于每一组中选多个的情况我们可以用二进制来枚举每一种可能。同时本题的一个难点是如何分好组。我们可以利用vector来解决（详细看代码）

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define w first
#define v second

using namespace std;

typedef pair<int, int> PII;

const int N = 60, M = 32010;

int n, m;
PII master[N];
vector<PII> sv[N];
int f[M];

int main(){
    cin>>m>>n;
    
    for(int i = 1 ; i <= n ; ++i){
        int w , v ,q;
        cin>>w>>v>>q;
        if(!q)master[i] = {w , w*v};
        else  sv[q].push_back({w,w*v});
    }
    
    for(int i = 1 ; i <= n ; ++i){
        if(master[i].first)
            for(int j = m ; j >= 0  ; --j){
                int len = sv[i].size();
                for(int k = 0 ; k < 1 << len;++k){
                    int w = master[i].first , v = master[i].second;
                    for(int u =  0; u < len;++u)
                        if( k >> u & 1) w += sv[i][u].w , v += sv[i][u].v;
                    if(j >= w)f[j] = max(f[j] , f[j-w] + v);
                }
            }
    }
        cout<<f[m]<<endl;
    return 0;
}

背包求解最优方案数

题目转送门

之前我们求的方案数是只考虑了体积，表示的是装满背包的方案数。而这题是求的是最优解（最大值）的方案数。
动态规划之背包模型及其扩展应用

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010 , mod = 1e9 + 7;
int n , m;
int f[N] ,c[N];

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

背包求解具体方案

题目转送门

解题思路：
一般来说求方案的话，一种方法是倒推和在dp的时候记录。这里我们依据01背包的式子进行倒推。
动态规划之背包模型及其扩展应用
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n , m ;
int w[N] , v[N];
int f[N][N] , way[N];

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

然后有一些数据被卡了，发现题目要的是字典序最小，这就是很恶心了。一般对于字典序最小我们都是通过贪心来解决。对于这题就是从前往后询问每一个物品，
动态规划之背包模型及其扩展应用
如果按照平时的背包问题我们是从前往后遍历的，那么我们在倒推的时候就需要从后往前这样就不符合贪心的原则了。因此我们在dp的时候倒着堆。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示从第i个物品开始体积不超过j的最大价值。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n , m ;
int w[N] , v[N];
int f[N][N] , way[N];

int main(){
     cin>>n>>m;
     
     for(int i = 1 ; i <=  n ; ++i)cin>>w[i]>>v[i];
     
     for(int i = n ; i >= 1 ; --i)
        for(int j = 0 ; j <= m ; ++j){
            f[i][j] = f[i+1][j];
            if(j >= w[i])
                f[i][j] = max(f[i][j] , f[i+1][j-w[i]] + v[i]);
        }
    
    int j = m;
    for(int i = 1 ; i <= n  ; ++i)
            if(j >= w[i] && f[i][j] == f[i+1][j-w[i]] + v[i])
                way[i] = 1 , j -= w[i];
    for(int i = 1 ; i <= n ; ++i)
        if(way[i])cout<<i<<" ";
    return 0;
}
上一篇：Flutter 去除右上角Debug标签


下一篇：第七次实验