【C++天梯计划】1.6 动态规划(DP dynamic programming)

🎆🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎆
今天我要开启一个新计划----【C++天梯计划】
目的是通过天梯计划，通过题目和知识点串联的方式，完成C++复习与巩固。

什么是动态规划？

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 关于动态规划最经典的问题当属背包问题。

动态规划性质

1.最优子结构性质。 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2.子问题重叠性质。 子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
3.无后效性。 即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

动态规划步骤

划分： 按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的
确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性
确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程
边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件。
即： 【初始状态】→【决策1】→【决策2】→…→【决策n】→【结束状态】

例题1：数塔问题

题目描述

有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

输入

输入数据首先包括一个整数整数 NN (1 \le N \le 1001≤N≤100)，表示数塔的高度，接下来用 NN 行数字表示数塔，其中第 ii 行有个 ii 个整数，且所有的整数均在区间 [0,99][0,99] 内。

输出

从底层走到顶层经过的数字的最大和是多少？

输入输出样例

输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
30

思路

将数塔存入二维数组，从倒数第2层开始，递推计算出走到每个点最多能够累计的最大数字和，直到第1层，就能求出所经过结点的数字和的最大值

代码：

#include
using namespace std;
int a[110][110];

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
       for(int j=1;j<=i;j++){
           cin>>a[i][j];
       }
    }
    //从倒数第2层开始逆推，每个点累加下方的值和下方右边的值中的较大值
    for(int i=n-1;i>=1;i--){
       for(int j=1;j<=i;j++){
           if(a[i+1][j]>a[i+1][j+1]){
              a[i][j] = a[i][j] + a[i+1][j];
           }else{
              a[i][j] = a[i][j] + a[i+1][j+1];
           }
       }
    }
    cout<<a[1][1];
    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
25

例题2:多重背包

题目描述

有N种物品和一个容量是V的背包。
第i种物品最多有si件，每件体积是vi，价值是wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
0 0

输出

输出一个整数，代表最大价值。

输入输出样例

输入
4 10
3 2 2
4 3 2
2 2 1
5 3 4
输出
8

方法1

思路 ：将多重背包的si个物品分别装入w和v数组，直接转换为01背包。
01背包：每种物品有1件
完全背包：每种物品有无限件数
多重背包：每种物品有Si件
解题思路：将多重背包转换为01背包
将Si件物品都存起来，转换为有Si个物品，每个物品有1件

#include 
using namespace std;
int n,c;//c背包容量
int v[10010],w[10010];
int dp[110];
int vi,wi,si,k;//k代表数组下标 
int main(){
	cin>>n>>c;
	for(int i = 1;i <= n;i++){
		cin>>vi>>wi>>si;
		//第i个物品有si件，都存入数组 
		for(int j = 1;j <= si;j++){
			k++;
			v[k] = vi;
			w[k] = wi;
		}
	}
	
	//01背包
	for(int i = 1;i <= k;i++){
		//逆序从背包容量循环到当前物品体积
		for(int j = c;j >= v[i];j--){
			dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
		} 
	} 
	
	cout<<dp[c];
	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
25
26
27
28
29

方法2：

思路：在做01背包时，体现一下有Si件物品这个条件。
01背包：每种物品有1件
完全背包：每种物品有无限件数
多重背包：每种物品有Si件
解题思路：将多重背包转换为01背包
将Si件物品都存起来，转换为有Si个物品，每个物品有1件

#include 
using namespace std;
int n,c;//c背包容量
int v[110],w[110],s[110];
int dp[110];
int main() {
    cin>>n>>c;
    for(int i = 1; i <= n; i++) {
        cin>>v[i]>>w[i]>>s[i];
    }
 
    //01背包
    //有n个物品
    for(int i = 1; i <= n; i++) {
        for(int k = 1;k <= s[i];k++) {
            //逆序从背包容量循环到当前物品体积
            for(int j = c; j >= v[i]; j--) {
                dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
 
    }
 
    cout<<dp[c];
    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
25
26