[动态规划]背包问题

动态规划之背包问题

背包：01背包，完全背包，多重背包。

01背包：动态规划之背包问题基础。核心就是物品只能取一次。

完全背包：01背包PLUS版本，核心是物品可以无限取。

多重背包：01背包的PLUSSS版本，核心是物品i可以取k[i]次。

混合背包：（mixb(ei)包）就是合了上述三种背包。

分组背包：分成多组的背包。

01背包：

简单来说就是，给你一堆东西，每个东西最多能拿取一次，就是对于第i种物品，你可以选择将其放入背包中，也可以选择不放入。可以简化成这么一个题目：

1	`给定n个物品，第i个物品的重量为weigh[i],价值为value[i]，现在给定一个容量为k的背包，，要求这个背包的所能装的最大价值。`

已知第i个物品的重量为w[i],价值为v[i],以及背包的总容量为k。

假设DP状态dp(i,j)为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。接下来就是考虑如何状态转移。假设已经处理好了前i-1个物品的所有状态，如果第i个物品不放入背包，则背包容量不会变化，其内包含的价值也不会改变，如果第i个物品放入背包就会出现两种情况，可能是$dp(i-1,j)$最大，也有可能是$dp(i-1,j-w[i])+v[i]$.也就是

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$

当然了，如果数据比较大的话，二维数组可能会MLE，我们发现可能dp(i)只和dp(i-1)有关，所以可以利用滚动数组将他压缩到一维，就是

$dp[j]=max(dp[j],dp[j-w[i]]+v[i])$

这样就可以了。代码实现如下：

#define int long long 
const int N=2e5+10;
int w[N],v[N],dp[N];
int k
for(int i=1;i<=n;i++){
    for(int j=k;j>=w[i];j++){
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

例题：# P1048 [NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入

输出 #1

说明/提示

【数据范围】

对于 $30\%$ 的数据，$M \le 10$；
对于全部的数据，$M \le 100$。

【题目来源】

NOIP 2005 普及组第三题

实现代码如下：

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

完全背包：

完全背包本质上和01背包差不多，但是它的其中一个物品可以选取无限次。

我们仍然假定，背包中前$i$种物品的状态为$dp(i,j)$，容量为j的背包所能够带来的最大价值。

同01背包一样，再假设第i种物品能选择k个。

$dp[i][j]=max(k->+00)(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])$

但是这种的话会出现O($n^3$)的时间复杂度，所以我们必须优化。很难想到可以优化成01背包的式子：

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$

同理，可以优化成一维的

$dp[j]=max(dp[j],dp[j-w[i]]+v[i])$

但是，完全背包的遍历和01背包是相反的(对于j的循环)。

看例题：

题目描述(p1616)

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例 #1

输入 #1

输出 #1

数据规模与约定

对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

for(int i=1;i<=n;i++){
    for(int j=w[i];j<=W;j++){
        if(dp[j-w[i]]+v[i]>dp[j])
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
     }
}

多重背包：

多重背包也是01背包的变种，指的是第$i$种物品最多可以取$k[i]$次。

实际上这种背包能够完完全全地转化为01背包。在双层循环时再加一个

1	`for(int m=0;m<=k[i];k++)`

这样以来就解决了，状态转移方程如下：

$dp[i][j]=max(0->k[i])(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])$

同样的可以滚动数组来到一维。

$dp[j]=max(0->k[i])(dp[j],dp[j-k*w[i]]+k*v[i])$

代码实现如下：

for(int i=1;i<=n;i++){
    for(int j=W;j>=w[i];j--){
        for(int m=1;m*w[i]<=W&&m<=k[i];m++){
            dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])
        }
    }
}

下面看例题：

P1833 樱花

题目描述

爱与愁大神后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i(0 \le C_i \le 200)$。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $P_i(0 \le P_i \le 100)$ 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 $T_i(0 \le T_i \le 100)$。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共 $n+1$行：

第 $1$ 行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），爱与愁大神院子里有几棵樱花树 $n$。这里的 $T_s$，$T_e$ 格式为：hh:mm，其中 $0 \leq hh \leq 23$，$0 \leq mm \leq 59$，且 $hh,mm,n$ 均为正整数。

第 $2$ 行到第 $n+1$ 行，每行三个正整数：看完第 $i$ 棵树的耗费时间 $T_i$，第 $i$ 棵树的美学值 $C_i$，看第 $i$ 棵树的次数 $P_i$（$P_i=0$ 表示无数次，$P_i$ 是其他数字表示最多可看的次数 $P_i$）。

输出格式

只有一个整数，表示最大美学值。

输入输出样例 #1

输入 #1

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出 #1

说明/提示

$100\%$ 数据：$T_e-T_s \leq 1000$（即开始时间距离结束时间不超过 $1000$ 分钟），$n \leq 10000$。保证 $T_e,T_s$ 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 $2$ 次。

int dp[N];
int w[N],v[N],k[N];
void solve(){
    string s1,s2;
    cin>>s1>>s2>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>k[i];
    }
    auto check=[&](string s){
        for(int i=0;i<s.size();i++){
            if(s[i]==':') return i;
        }
    };
    auto summ=[&](string s){
        int q=check(s);
        if(q==1){
            return (s[0]-'0')*60+(s[2]-'0')*10+s[3]-'0';
        }else{
            return ((s[0]-'0')*10+s[1]-'0')*60+(s[3]-'0')*10+s[4]-'0';
        }
    };
    auto trans=[&](string s1,string s2){
        int res1=summ(s1);
        int res2=summ(s2);
        return res2-res1;
    };
    int T=trans(s1,s2);
    for(int i=1;i<=n;i++){
        if(k[i]==0){
            for(int j=w[i];j<=T;j++){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }else{
        for(int j=1;j<=k[i];j++){
            for(int l=T;l>=w[i];l--){
                dp[l]=max(dp[l],dp[l-w[i]]+v[i]);
                }
            }
        }
    }
    cout<<dp[T]<<endl;
}

混合背包：

（上面那个题就是混合背包）实际上就是把上面三个背包：01背包，完全背包和多重背包结合起来了。处理的方式也是很简单：

for(int i=1;i<=n;i++){
    if(满足01背包的条件){
        for(int j=w[i];j<=W;j++){
            ......
        }
    }
    else if(满足完全背包的条件){
        for(int j=W;j>=w[i];j--){
            ......
        }
    }
    else{//剩下的就是多重背包
        for(int j=1;j<=k[i];j++){
            for(int m=W;m>=w[i]*j;m--){
                ......
            }
        }        
    }
}

只用分部枚举这三种背包的模式就可以了。

分组背包：

分组背包中的物品通常是有写属于那个背包的，我们不妨先输入所有的物品后，再根据其种类再分别在该种类中取其中一件。然后就转变成了01背包。

首先是如何存储组数：

vector<vector<pair<int,int>>> v(101);
for(int i=1;i<=n;i++){
    int w,val,k//占地，价值，组别
    v[k].pb({w,val});
}

例题：

P1757 通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

代码如下：

void solve(){
    cin>>m>>n;
    vector<vector<pair<int,int>>> v(101);
    for(int i=1;i<=n;i++){
        int w, val, k;
        cin>>w>>val>>k;
        v[k].pb({w,val});
    }
    for(int k=1;k<=100;k++){
        for(int i=m;i>=0;i--){
            for(auto [w,val]:v[k]){
                if(i>=w){
                    dp[i]=max(dp[i],dp[i-w]+val);
                }
            }
        }
    }
    cout<<dp[m]<<endl;
}

#动态规划

[动态规划]背包问题

http://example.com/2025/03/07/动态规划-背包问题/

Author

Bai_qiuyue

Posted on

March 7, 2025

Licensed under

[动态规划]动态规划入门 Previous

[数论]费马小定理 Next