自学内容网 自学内容网

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

OI Wiki 上的详细讲解

模型总结

分组背包的问题模板:有 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[i1][jv[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 1n4 1 ≤ m ≤ 4 1 \leq m \leq 4 1m4

对于 50% 的数据, 1 ≤ n ≤ 100 1 \leq n \leq 100 1n100 1 ≤ m ≤ 100 1 \leq m \leq 100 1m100

对于 100% 的数据, 1 ≤ n ≤ 100 1 \leq n \leq 100 1n100 1 ≤ m ≤ 100 1 \leq m \leq 100 1m100

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[i1][jk.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)!