模型总结
分组背包的问题模板:有 n n n 件物品和一个大小为 m m m 的背包,第 i i i 个物品的价值为 w i w_i wi,体积为 v i v_i vi。同时,每个物品属于一个组,同组内最多只能选择一个物品。求背包能装载物品的最大总价值。
我们也可以说得高大上一点:有若干组物品,每组内的物品之间互斥。求最大背包价值。
分组背包的 dp 状态: d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 件物品,背包容量为 j j j 达到的最大价值
设 v [ i ] [ k ] v[i][k] v[i][k] 和 w [ i ] [ k ] w[i][k] w[i][k] 分别表示第i组第 k k k 个物品的体积、价值, s [ k ] s[k] s[k] 表示第 k k k 个组的元素数量,则转移如下:
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] } dp[i][j]=max\{dp[i-1][j-v[i][k]]+w[i][k]\} dp[i][j]=max{dp[i−1][j−v[i][k]]+w[i][k]} 1 < = i < = n , v [ i ] [ k ] < = j < = m , 1 < = k < = s [ k ] 1<=i<=n,v[i][k]<=j<=m,1<=k<=s[k] 1<=i<=n,v[i][k]<=j<=m,1<=k<=s[k]
d p [ n ] [ m ] dp[n][m] dp[n][m] 即为答案(和 01 背包很像)
同理,也可以压成一维数组,注意压维后背包容量( j j j)要倒着枚举,避免从已经更新的地方(同一行)转移。
不能从同一行转移的原因是:分组背包每一组只能选一个,如果从同一组转移的话就变成了“分组完全背包”(这个名是我胡诌的)
例1.小明爱上课
Description
小明非常喜欢上课,现在小明的课表有一些课,他可以通过课表选择上哪些课。
上课会有奖励,每门课上课时间长短不同奖励也会不一样,存在上课时间更长,奖励更少的情况。每一门课上课的总时长为整数。不同时长的奖励,题目数据中会给出。
对于每一门课,小明只可以上一次,现在小明一共有 m m m 分钟的时间可以安排上课,但是小明想要得到最大的奖励,聪明的你可以帮助小明解决这个问题吗?
Input Format
第一行,输入两个数 n n n 和 m m m ,表示课程的数目以及小明需要上课的时间。接下来包括 n n n 行,每行 m m m 个数,第 i i i 个数表示对于每门课上 i i i 分钟的奖励( i i i 从 1 开始,每门课程只可以上一次)。
Output Format
输出一个数,表示最大的奖励值。
输入数据 1
2 3
3 2 1
3 2 1
输出数据 1
6
Hint
数据范围
对于 10% 的数据, 1 ≤ n ≤ 4 1 \leq n \leq 4 1≤n≤4 , 1 ≤ m ≤ 4 1 \leq m \leq 4 1≤m≤4
对于 50% 的数据, 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 , 1 ≤ m ≤ 100 1 \leq m \leq 100 1≤m≤100
对于 100% 的数据, 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 , 1 ≤ m ≤ 100 1 \leq m \leq 100 1≤m≤100
1 ≤ 1 \leq 1≤ 奖励值 ≤ 1000 \leq 1000 ≤1000
样例说明
这里小明一共有三分钟,他第一门课上一分钟得到 3 个奖励值,第二门课上一分钟得到 3 个奖励值,最多得到了 6 个奖励值,这个时候还剩一分钟,他这一分钟可以选择不上课,因为这个时候也没有课可以上了,如果选择其他的方案的话这个最大奖励值会降低。
这是一道模板题,直接按照模板里的思路敲代码就行。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[105][105];
int dp[105][1005]; // dp[i][j]表示前i节课,还能上的时间为j分钟的最大奖励值
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
dp[0][0] = 0; // 初始化:前0节课,上了0分钟的奖励值是0(这一句不要也可以,但严谨起见可以加上)
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){ // 注意这里枚举的是上课时间
dp[i][j] = dp[i - 1][j]; // 先赋值为上一次的值(不能放到下面的循环里,因为这样会导致多次赋值为这个值,会出错)
for(int k = 1; k <= m; k ++){ // 这里枚举的是a的下标
if(j >= k) dp[i][j] = max(dp[i - 1][j - k] + a[i][k], dp[i][j]);
}
}
}
cout << dp[n][m] << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
Code2(压维)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[105][105];
int dp[1005]; // dp[j]表示当前还能上的时间为j分钟的最大奖励值
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
dp[0] = 0; // 初始化:前0节课,上了0分钟的奖励值是0(这一句不要也可以,但严谨起见可以加上)
for(int i = 1; i <= n; i ++){
for(int j = m; j >= 1; j --){ // 注意这里倒着枚举,避免从相同的行更新(因为分组背包一组只能选一个)
for(int k = 1; k <= m; k ++){
if(j >= k) dp[j] = max(dp[j - k] + a[i][k], dp[j]);
}
}
}
cout << dp[m] << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
例2.[ABC344D] String Bags
问题陈述
最初有一个空字符串 S S S。 此外,还有 1 , 2 , … , N 1, 2, \ldots, N 1,2,…,N 个包,每个包都包含一些字符串。 袋子 i i i 包含 A i A_i Ai 个字符串 S i , 1 , S i , 2 , … , S i , A i S_{i,1}, S_{i,2}, \ldots, S_{i,A_i} Si,1,Si,2,…,Si,Ai。
对于 i = 1 , 2 , … , N i = 1, 2, \ldots, N i=1,2,…,N,您将重复以下步骤:
选择并执行以下两个操作之一:
- 支付 1 日元,从 i i i 中选择一个字符串,并将其连接到 S S S 的末尾。
- 什么也不做。
给定字符串 T T T,求使最后的 S S S 等于 T T T 所需的最小金额。 如果无法使最后的 S S S 等于 T T T,则打印 -1。
限制因素
- T T T 是一个由小写英文字母组成的字符串,长度在 1 和 100 之间(含)。
- N N N 是介于 1 和 100 之间的整数,包含在内。
- A i A_i Ai 是介于 1 和 10 之间的整数,包括首尾两个整数。
- S i , j S_{i,j} Si,j 是由小写英文字母组成的字符串,长度在 1 和 10 之间(包括首尾数字)。
输入
输入内容由标准输入法提供,格式如下:
T
N
A_1
S_{1,1}
S_{1,2}
…
S_{1,A_1}
A_2
S_{2,1}
S_{2,2}
…
S_{2,A_2}
⋮
A_N
S_{N,1}
S_{N,2}
…
S_{N,A_N}
输出
将答案打印为整数。
题目描述
あなたは最初、空文字列 $ S $ を持っています。
さらに、文字列がいくつか入った袋 $ 1,2,\dots,N $ があります。
袋 $ i $ には $ A_i $ 個の文字列 $ S_{i,1},S_{i,2},\dots,S_{i,A_i} $ が入っています。
これから、以下の手順を $ i=1,2,\dots,N $ について繰り返します。
- 以下のふたつの行動のうち、どちらかを選択して行う。
- $ 1 $ 円を支払い、袋 $ i $ からちょうどひとつの文字列を選択して $ S $ の末尾に連結する。
- 何もしない。
文字列 $ T $ が与えられるとき、最終的に $ S $ と $ T $ を一致させるために必要な最小の金額を求めてください。
但し、どのようにしても最終的な $ S $ を $ T $ に一致させることができない場合、 -1
と出力してください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ T $ $ N $ $ A_1 $ $ S_{1,1} $ $ S_{1,2} $ $ \dots $ $ S_{1,A_1} $ $ A_2 $ $ S_{2,1} $ $ S_{2,2} $ $ \dots $ $ S_{2,A_2} $ $ \vdots $ $ A_N $ $ S_{N,1} $ $ S_{N,2} $ $ \dots $ $ S_{N,A_N} $
输出格式
答えを整数として出力せよ。
样例 #1
样例输入 #1
abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de
样例输出 #1
2
样例 #2
样例输入 #2
abcde
3
2 ab abc
3 f c bcde
1 e
样例输出 #2
-1
样例 #3
样例输入 #3
aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc
样例输出 #3
4
提示
制約
- $ T $ は長さ $ 1 $ 以上 $ 100 $ 以下の英小文字からなる文字列
- $ N $ は $ 1 $ 以上 $ 100 $ 以下の整数
- $ A_i $ は $ 1 $ 以上 $ 10 $ 以下の整数
- $ S_{i,j} $ は長さ $ 1 $ 以上 $ 10 $ 以下の英小文字からなる文字列
Sample Explanation 1
例えば、以下のようにすると $ 2 $ 円で最終的な $ S $ と $ T $ を一致させることができ、これが必要な金額の最低値であることが示せます。 - $ i=1 $ について、袋 $ 1 $ から abc
を選択し $ S $ の末尾に連結する。 $ S= $ abc
となる。 - $ i=2 $ について、何もしない。 - $ i=3 $ について、袋 $ 3 $ から de
を選択し $ S $ の末尾に連結する。 $ S= $ abcde
となる。
Sample Explanation 2
どのようにしても最終的な $ S $ と $ T $ を一致させることができないので、 -1
と出力してください。😊
解题思路
这道题有点意思。是一道字符串背景下的背包问题。当然,也是分组背包。
这道题是针对字符串进行操作,我们可以进行题面转换,换成我们熟悉的样子。
把拼接的字符串转化为得到的价值,“还能拼接多长的字符串”转化为背包的剩余容量。
设dp[i][j]表示前i个组,“还能拼接的字符串长度”j的最小代价,则转移如下:
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j − k . s i z e ( ) ] + 1 } dp[i][j] = max\{dp[i-1][j-k.size()]+1\} dp[i][j]=max{dp[i−1][j−k.size()]+1}
且仅当 “字符串k是目标字符串T中以位置j为结尾的子串” 时
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string T;
vector <string> s[105];
int n, a[105], dp[105][105];
// 字符串k是否为目标字符串T中以位置pos为结尾的子串
int check(int pos, string k){
// if(k.size() > pos+1) return 0; // 避免越界。因为string下标从0开始,所以是>=pos+1
// 这里可以举个例子:T="abcd" pos=2;如果k.size()<=3则可以,否则不行
for(int i = pos, j = k.size() - 1; i >= pos - (k.size() - 1) && j >= 0; i --, j --){ // i是T的指针、j是k的指针
// i的范围可以尝试一下:T="abcd" k="bc" pos=2,则应该从2遍历到1,即pos ~ pos-(k.size()-1)
if(T[i] != k[j]) return 0;
}
return 1;
}
void solve()
{
cin >> T >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
for(int j = 0; j < a[i]; j ++){
string tmp; cin >> tmp; s[i].push_back(tmp);
}
}
// 初始化
memset(dp, 127, sizeof dp); // memset按照字节赋值,int有4字节,每个字节8比特。127二进制为(0111 1111)2,刚好可以把整个字节大体填满
for(int i = 0; i <= n; i ++) dp[i][0] = 0; // !!!初始化:前i个,长度为0,要花的钱为0
// dp
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= T.size(); j ++){
dp[i][j] = dp[i - 1][j]; // 初始化一下,注意!不能发放在下面的循环中,这样每次循环都重新初始化一遍,会出错
for(string k : s[i]){
if(j < k.size() || check(j - 1, k) == 0) continue; // 不符合要求
dp[i][j] = min(dp[i][j], dp[i - 1][j - k.size()] + 1); // string下标从0开始,所以k.size()要-1
}
}
}
int ans = dp[n][T.size()];
cout << (ans == 2139062143? -1 : ans) << '\n'; // 输出答案
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
End
这里是 YLCHUP,谢谢大家!