dp笔记

dp问题

满足最优子结构:不管过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。

无后效性:以前各阶段的状态无法直接影响它未来的决策。

背包问题

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
i 件物品的体积是 v_i,价值是 w_i
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 v_i, w_i,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000

0<vi,wi≤1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

int n,m;
int w[1010],v[1010];
int f[1010][1010];

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++){
if(j<w[i]) f[i][j]=f[i-1][j];
else{
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
cout<<f[n][m];
return 0;

}

当每种类别有s个物品,多重背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;
int f[N][N]={};
int s[N],v[N],w[N];

int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=s[i];k++){
if(j<k*v[i]) f[i][j]=f[i-k][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m];
return 0;
}

摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

1.gif

输入格式

第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100 , 1≤R,C≤100 , 0≤M≤1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;

int f[N][N];

int a[N][N];
int n,m;

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

偷商店

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入格式

输入的第一行是一个整数 T,表示一共有 T 组数据。接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数元。

每家店铺中的现金数量均不超过1000。

imput tamples:

2

3

1 8 2

4

10 7 6 14

result:

8

24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int rob(vector<int>& money){
int dp[200]={};
dp[0]=money[0];
int n=money.size();
for(int i=1 ;i<n;++i){
if(i==1){
dp[1]=max(money[0],money[1]);
}
else{
dp[i]=max(dp[i-1],dp[i-2]+money[i]);
}
}
return dp[n-1];
}

int main(){
int n;
cin>>n;
vector<int> money;
vector<vector<int> > group;
int i;
int tem=n;
vector<int> res;
int a[50];
while(tem!=0){
cin>>a[tem];
while (cin>>i){
money.push_back(i);
if(cin.get()=='\n') break;
}
group.push_back(money);
money.clear();
tem--;
}
while(tem!=n){

res.push_back(rob(group[tem]));
tem++;
}
vector<int>::iterator it;
for(it=res.begin();it!=res.end();++it)
cout<<*it<<endl;
return 0;
}

地宫取宝

X 国王有一个地宫宝库,是 n×m个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。

地宫的入口在左上角,出口在右下角。

小明被带到地宫的入口,国王要求他只能向右或向下行走。

走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。

当小明走到出口时,如果他手中的宝贝恰好是 k
件,则这些宝贝就可以送给小明。

请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k件宝贝。

输入格式

第一行 3
个整数,n,m,k
,含义见题目描述。

接下来 n
行,每行有 m
个整数 Ci
用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数,表示正好取 k
个宝贝的行动方案数。

该数字可能很大,输出它对 1000000007
取模的结果。

数据范围

1≤n,m≤50
,
1≤k≤12
,
0≤Ci≤12
![]/img/(image-4.png)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=55, MOD =100000007;

int n,m,k;
int w[N][N];
int f[N][N][13][14];

int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
w[i][j]++;
}
}

f[1][1][1][w[1][1]]=1;
f[1][1][0][0]=1;

for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int u=0;u<=k;u++){
for(int v=0;v<=13;v++){
int &val=f[i][j][u][v];
val=(val+f[i-1][j][u][v])%MOD;
val=(val+f[i][j-1][u][v])%MOD;
if(u>0&& v==w[i][j]){
for(int c=0;c<v;c++){
val=(val+f[i-1][j][u-1][c])%MOD;
val=(val+f[i][j-1][u-1][c])%MOD;
}
}
}
}
}
}
int res=0;
for (int i=0;i<=13;i++) res=(res+f[n][m][k][i])%MOD;
cout<<res;
return 0;

}

dp笔记
http://example.com/2024/02/05/dp笔记/
作者
邓骏韬
发布于
2024年2月5日
许可协议