C++分组背包问题_动态规划dp_背包_算法竞赛

OI Wiki 上的详细讲解

模型总结

分组背包的问题模板：有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w_i$，体积为 $v_i$。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

我们也可以说得高大上一点：有若干组物品，每组内的物品之间互斥。求最大背包价值。

分组背包的 dp 状态：$dp[i][j]$ 表示前 $i$ 件物品，背包容量为 $j$ 达到的最大价值

设 $v[i][k]$ 和 $w[i][k]$ 分别表示第i组第 $k$ 个物品的体积、价值，$s[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]$$

$dp[n][m]$ 即为答案（和 01 背包很像）

同理，也可以压成一维数组，注意压维后背包容量（$j$）要倒着枚举，避免从已经更新的地方（同一行）转移。
不能从同一行转移的原因是：分组背包每一组只能选一个，如果从同一组转移的话就变成了“分组完全背包”（这个名是我胡诌的）

例1.小明爱上课

Description

小明非常喜欢上课，现在小明的课表有一些课，他可以通过课表选择上哪些课。

上课会有奖励，每门课上课时间长短不同奖励也会不一样，存在上课时间更长，奖励更少的情况。每一门课上课的总时长为整数。不同时长的奖励，题目数据中会给出。

对于每一门课，小明只可以上一次，现在小明一共有 $m$ 分钟的时间可以安排上课，但是小明想要得到最大的奖励，聪明的你可以帮助小明解决这个问题吗？

Input Format

第一行，输入两个数 $n$ 和 $m$ ，表示课程的数目以及小明需要上课的时间。接下来包括 $n$ 行，每行 $m$ 个数，第 $i$ 个数表示对于每门课上 $i$ 分钟的奖励（$i$ 从 1 开始，每门课程只可以上一次）。

Output Format

输出一个数，表示最大的奖励值。

输入数据 1

2 3
3 2 1
3 2 1

输出数据 1

6

Hint

数据范围

对于 10% 的数据，$1\le n\le 4$ ，$1\le m\le 4$

对于 50% 的数据，$1\le n\le 100$ ，$1\le m\le 100$

对于 100% 的数据，$1\le n\le 100$ ，$1\le m\le 100$

$1\le$ 奖励值 $\le 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$。 此外，还有 $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$ 是一个由小写英文字母组成的字符串，长度在 1 和 100 之间（含）。
• $N$ 是介于 1 和 100 之间的整数，包含在内。
• $A_i$ 是介于 1 和 10 之间的整数，包括首尾两个整数。
• $S_{i,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，谢谢大家！

原文地址：https://blog.csdn.net/YLCHUP/article/details/140579256

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！