《动态规划 ---- 线性规划一》----- 动态规划的基本概念，线性动态规划--＞背包问题

1，引入

首先什么是动态规划问题？什么是动态规划？我们要认识到在算法竞赛中我们所涉及到的问题通常要使用一些算法思想，在前面我们提到的有一些分治、贪心、等等的算法思想，毫无疑问DP也是一种算法思想，和前面几种算法思想不同的是，DP似乎更细化在一些更加难解决的问题中出现，所以我们会在下面的章节中花费至少两周的时间来准备这方面的知识。

2，动态规划的定义

2，1动态规划到底是什么？

对于一些算法问题，我们在选择的过程中可能会涉及到很多的路径，如果我们尝试去直接向下的搜索，如果路径非常多，直接爆掉。这样我们就需要一种算法思想来优化这个寻找路径的过程，这里设计到了两个思想：

问题解决无后延性
重叠子问题
我们把一个大的问题转化成一些小的问题的，我们每次都进行分步的来看，选择分布出来的最优化的结构，或者是对当前的状态或者是对当前的相关的内容。

2、2动态规划的基本的结构

虽然动态规划是一种复杂的算法思想，但是我们还是总结出来了一些基本的套路，在我们刚刚进行DP的学习的时候，我们可以使用下面的思路完成一些对DP的基础理解

DP ： 状态表示 + 状态转移方程

3,线性DP

1，线性DP的定义

首先是线性DP的基础的定义，线性DP就是一种最为简单的DP的操作，我们需要总结一些操作来完成对DP的学习

2，典型的线性DP问题

思路一 ： 回顾原来多个状态，不仅回顾n-1状态，可以回顾多个状态n-2,n-3。我们提前进行几个初始值的计算。我们要大胆的猜想才能找到DP的学习思路。

最经典问题 —— 背包问题

首先是线性背包问题，我们的线性DP问题中最为经典的问题就是背包问题，首先我们知道背包问题分成好多种背包问题，我们首先来分析下面几种背包问题，来帮助我们理解背包模型。

首先是01背包问题，01背包acwing跳转

过题代码

/*
    1.算法名称 ： 动态规划 ———— 线性规划问题 --- 01背包问题
    2.
     >算法时间复杂度 ： 一般情况下不会少于O(N^2)
     > 空间复杂度 ： 我们知道空间最多能开到 3e7 的大小 ，正好是 240MB 
    3. 代码思路 ： 
    本题使用了滚动数组的空间的优化方法,空间会变得更加小。
        状态表示 ： dp[滚动数组][N == 当前背包的体积 ]  , 所代表的值 --->>> 当前背包体积下能最多获得的价值
        状态转移方程 ： 状态转移方程 dp[now][j] = max(dp[old][j - x] + y , dp[old][j]) ; // 每次都
        让转移之后的状态变得最大。
    解决的问题 ： 01背包问题 ; 
*/
    

#include 
using namespace std ;

const int N = 10010 ; 

int dp[2][N] ; 

int main ()
{
    int n , m ;
    cin >> n >> m;
    int now = 0 , old = 1 ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int x , y ;
        cin >> x >> y ;
        swap(now , old) ; 
        for(int j = x ; j <= m ; j ++ )
        {
            dp[now][j] = max(dp[old][j - x] + y , dp[old][j]) ; 
        }
    }
    cout << dp[now][m] << endl ; 
    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
30
31
32
33
34
35
36
37
38
39

完全背包问题 ： acwing完全背包问题跳转

过题代码

/*
    1.算法名称 ： 动态规划 ———— 线性规划问题 --- 完全背包问题
    2.
     >算法时间复杂度 ： 一般情况下不会少于O(N^2)
     > 空间复杂度 ： 我们知道空间最多能开到 3e7 的大小 ，正好是 240MB 
    3. 代码思路 ： 
    本题使用了滚动数组的空间的优化方法,空间会变得更加小,我们使用的是自身滚动的方式。
        状态表示 ： dp[N == 当前背包的体积 ]  , 所代表的值 --->>> 当前背包体积下能最多获得的价值
        状态转移方程 ： 状态转移方程  dp[i] = max(dp[i] , dp[i - vi] + wi) ;  // 每次都
        让转移之后的状态变得最大,我们只要使用反搜就行。
    解决的问题 ： 完全背包问题 ; 
*/
    

#include 
using namespace std ;

const int N = 1010 ; 

int dp[N] ; 

int main ()
{
    int n , v ;
    cin >> n >> v ;
    for(int i = 0 ; i < n ; i ++ )
    {
        int vi  , wi ; 
        cin >> vi >> wi ; 
        for(int i = vi ; i <= v ; i ++ )
        {
            dp[i] = max(dp[i] , dp[i - vi] + wi) ; 
        }
    }
    cout << dp[v] << endl ;
    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
30
31
32
33
34
35
36
37

3,多重背包问题 ------ 每个背包都有相关的个数acwing 连接的跳转

思路解析 ：

首先我们知道01背包的问题如何解决了，然后只要把多重背包问题转化成了01背包问题就能解决相关问题。

相关代码

/*
    1.算法名称 ： 动态规划 ———— 线性规划问题 --- 多重背包问题
    2.
     >算法时间复杂度 ： 一般情况下不会少于O(N^3)
     > 空间复杂度 ： 我们知道空间最多能开到 3e7 的大小 ，正好是 240MB 
    3. 代码思路 ： 
    本题使用了滚动数组的空间的优化方法,空间会变得更加小,我们使用的是自身滚动的方式。
        状态表示 ： dp[N == 当前背包的体积 ]  , 所代表的值 --->>> 当前背包体积下能最多获得的价值
        状态转移方程 ： 状态转移方程 本质上就是 01 背包问题 // 每次都选用其中的一个就行。 
        让转移之后的状态变得最大,我们只要使用反搜就行。
    解决的问题 ： 完全背包问题 ; 
*/
    

#include 
using namespace std ; 

int n , m ;

const int N = 10010 ; 
const int M = 2010 ; 
int v[N] , w[N] , cnt = 0 ; 
int f[N] ; 

int main ()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int x , y , z ;
        cin >> x >> y >> z ;
        int k = 1 ; 
        while ( k <= z)
        {
            v[++ cnt] = k * x ;
            w[cnt] = k * y ; 
            z -= k ; 
            k *= 2 ; 
            
        }
        if(z > 0)
        {
            v[++ cnt] = z * x ;
            w[cnt] = z * y ;
        }
        
    }n = cnt ; 
    for(int i = 1 ; i <= n ; i ++ )
    for(int j = m ; j >= v[i] ; j -- )
    f[j] = max(f[j] , f[j - v[i]] + w[i]) ; 
    cout << f[m] << endl ; 
    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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53