自娱自乐的精神乐园

余凯迪的博客

0%

动态规划

发表于 分类于 阅读次数：

动态规划

有限集中的最优化问题

  1. 状态表示（化零为整）
  • 确定集合是什么
  • 属性和集合的关系（max，min，count）
  1. 状态计算（化整为零）
  • 划分为不同的子集，计算子集然后根据子集计算该集合的属性（不重复不遗漏）
  • 划分依据：寻找最后一个不同点

示例

1. 01背包问题

普通的状态转移方式，二维的状态表示
状态 dp[i][j] 表示前i个物品体积不超过j的最大价值
状态转移：dp[i][j] = max(dp[i-1][j], dp[i-v[i]]+w[i])

朴素解答

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<cstring>
using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N][N];

int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=N;++i){
        cin>>v[i]>>w[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;++i){
        for(int j=0;j<=V;++j){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }
    cout<<dp[N][V];
    return 0;
}

状态优化解答

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

const int N=1010;
int v[N],w[N];
int dp[N];

int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=N;++i){
        cin>>v[i]>>w[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;++i){
        // 主要此时对体积的遍历，从小到大会影响到dp[j-v[i]]，从大到小保证更新j的时候，j-v[i]是 i-1 的值而不是 i 的值
        for(int j=V;j>=v[i];--j){
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout<<dp[V];
    return 0;
}

2. 完全背包问题

状态dp[i][j] 表示前i个物品体积不超过j的最大价值；
状态转移 dp[i][j]=max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2v]+2w, dp[i-1][j-3v]+3w, ...)
朴素的状态转移需要3重循环；考虑dp[i][j]和dp[i][j-v]的关系：
dp[i][j-v]=max(dp[i-1][j-v], dp[i-1][j-2v]+w, dp[i-1][j-3v]+2w,...)
可以看出dp[i][j]=max(dp[i-1][j], dp[i][j-v]+w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>

using namespace std;
const int N=1010;
int v[N],w[N];

int dp[N];

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

3. 石子合并

区间dp问题
状态表示：f(i,j)表示所有将[i,j]合并为一堆的方案的集合；属性为最小值
状态计算：
f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)) i≤k≤j-1

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>

using namespace std;

const int N = 310;

int v[N],f[N][N];
int pre_sum[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>v[i];
        // 先记录前缀和后续使用
        pre_sum[i] = pre_sum[i-1]+v[i];
    }
    // 先枚举区间，再枚举区间起点，再枚举区间分割点
    for(int len=2;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j= i+len-1;
            f[i][j] = 1e8;
            for(int k=i;k<=j-1;++k){
                f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+pre_sum[j]-pre_sum[i-1]);
            }
        }
    }
    cout<< f[1][n];
    return 0;
}

最长公共子序列

状态表示：f(i,j)
集合：A[1-i]和B[1-j]所有公共子序列的集合
状态：最大值
状态转移：

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

using namespace std;

const int N=1010;

char a[N],b[N];
int f[N][N];

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