精华内容
下载资源
问答
  • dp 第四章-动态规划例题分析第四章-动态规划例题分析第四章-动态规划例题分析第四章-动态规划例题分析
  • 动态规划例题

    千次阅读 2018-07-21 22:03:02
    看到《数学建模算法与应用(第二版)》第四章动态规划,发现书上例题都没源码,鉴于本人matlab太菜,而且matlab一个函数一个.m文件的尿性,我决定试试用python解决例题6,附上题目 例 6 设某工厂有 1000 台机器,...

    看到《数学建模算法与应用(第二版)》第四章动态规划,发现书上例题都没源码,鉴于本人matlab太菜,而且matlab一个函数一个.m文件的尿性,我决定试试用python解决例题6,附上题目

    例 6 设某工厂有 1000 台机器,生产两种产品 A、 B ,若投入 x 台机器生产 A 产品,则纯收入为5x ,若投入 y 台机器生产 B 种产品,则纯收入为 4y ,又知:生产 A 种产品机器的年折损率为 20%,生产 B 产品机器的年折损率为 10%,问在 5 年内如何安排各年度的生产计划,才能使总收入最高?


    书上手推算的过程如下:

    然后我以为半个小时能搞定的python代码我花了一晚上,附上源代码

    # xk 第k年初完好机器数
    # uk 第k年安排生产A种产品的机器数
    # xk-uk 第k年安排生产B种产品的机器数
    
    # 第k+1年初完好的机器数
    def x_k_Add_1(uk, xk):
        return (1 - 0.2) * uk + (1 - 0.1) * (xk - uk)
    
    
    # vk(xk,uk) 第k年的纯收入
    def vk(uk, xk):
        return uk + 4 * xk
    
    
    # fk(xk)第k年初往后各年的最大利润之和
    # 返回 以后最大值(xk倍数)
    def fk(k_Add_1_xk, k):
        if k == 6:
            k_Add_1_xk = 0
            par_u = 1
            par_x = 4
        else:
            par_u = 1 - k_Add_1_xk * 0.1
            par_x = 4 + k_Add_1_xk * 0.9
        max, uk = MAX(par_u, par_x)
        return max, uk
    
    
    # 寻找在第k年,总台数xk约束下的最大值
    # 返回:最大值(xk倍数),uk
    def MAX(par_u, par_x):
        if par_u >= 0:
            return par_u + par_x, 1
        else:
            return par_x, 0
    
    
    if __name__ == '__main__':
        k_Add_1_xk = 0
        max = 0
        uk = []
        for i in range(6, 0, -1):
            k_Add_1_xk, u_k = fk(k_Add_1_xk, i)
            uk.append(u_k)
        uk.reverse()
        max = k_Add_1_xk
        print("最大利润为:%.1f" % (max * 1000))
        x = 1000
        x_last = 0
        for i in range(1, 6):
            if i == 1:
                print("第" + str(i) + "年完好的机器数 %.1f" % x)
                x_last = x
                continue
            x = 0.9 * x - 0.1 * uk[i - 1] * x_last
            x_last = x
            print("第" + str(i) + "年完好的机器数 %.1f" % x)

    运行结果如下:

    最大利润为:19733.8
    第1年完好的机器数 1000.0
    第2年完好的机器数 900.0
    第3年完好的机器数 810.0
    第4年完好的机器数 648.0
    第5年完好的机器数 518.4

    ps.算法课动态规划没有实践的坑,现在终于算是填上了。。。出来混,迟早是要还的。。。。。。

    展开全文
  • 动态规划课件及动态规划经典例题讲解和分析。主要介绍动态规划算法的思想和例题分析
  • 关于动态规划的一些经典例题的详细讲解,和概念的分析
  • 分析:贪心算法不适用于此题,因为每一层的选择会影响到其下一层的选择,子解是相互影响的,很喜欢老师上课讲的一句话:在这题中我们不应该盲目地去取每一层的最优解,而是携带着先前的状态去做当前层的决策。...

    有形如下图的一个数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。

    在这里插入图片描述
    分析:贪心算法不适用于此题,因为每一层的选择会影响到其下一层的选择,子解是相互影响的,很喜欢老师上课讲的一句话:在这题中我们不应该盲目地去取每一层的最优解,而是携带着先前的状态去做当前层的决策。这很好地讲述了动态规划问题的精髓,我们由下而上的解决问题时,一要保存子问题的状态,二要利用子问题的状态解决当前问题。

    法一:自上而下的动态规划
    在这种动态规划中,起始点唯一,终点为n
    设置初始条件O(1) 取解O(n)
    由于数塔结构需要考虑边界条件

    #include <iostream>
    #include <algorithm>
    #define n 5
    
    using namespace std;
    
    int nums[n][n] = {
        {9},
        {12, 5},
        {10, 6, 8},
        {2, 18, 9, 5},
        {19, 7, 10, 4, 16}
    };
    
    int main() {
        int dp[n][n];
        int res = 0;
        dp[0][0] = nums[0][0];	// 初始条件:第一层只有一个节点 直接保存到dp
        for (int i = 1; i < n; i++) 
            for (int j = 0; j <= i; j++) 
                if (j == 0 || j == i)	// 边界条件:从塔尖到塔边路径唯一
                    dp[i][j] = (j == 0 ? dp[i - 1][j] : dp[i - 1][j - 1]) +  nums[i][j];
                else	// 状态转移:其余节点挑选来源的两条路径的较大值
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j];
    
        for (int j = 0; j < n; j++)	// 遍历出口取最大值
            if (dp[n - 1][j] > res)
                res = dp[n - 1][j];
        
        cout << "max:" << res << endl;	// 输出最大数值:59
        system("pause");
        return 0;
    }
    

    法二:自下而上的动态规划
    在这种动态规划中,起始点为n,终点唯一
    设置初始条件O(n) 取解O(1)
    不需要考虑边界条件

    #include <iostream>
    #include <algorithm>
    #define n 5
    
    using namespace std;
    
    int nums[n][n] = {
        {9},
        {12, 5},
        {10, 6, 8},
        {2, 18, 9, 5},
        {19, 7, 10, 4, 16}
    };
    
    int main() {
        int dp[n][n];
        int res = 0;
    
        for (int j = 0; j < n; j++)	// 初始条件:将底层的每个出发点 直接保存到dp数组
            if (dp[n - 1][j] > res)
                dp[n - 1][j] = nums[n - 1][j];
        
        for (int i = n - 2; i >= 0; i--)	// 边界条件:无
            for (int j = 0; j <= i; j++) // 状态转移:其余节点挑选来源的两条路径的较大值
                    dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + nums[i][j];
    
        res = dp[0][0];	// 终点唯一
        cout << "max:" << res << endl;
        system("pause");
        return 0;
    }
    

    总结:
    ①如需比较到达不同终点状态的各个路径时,使用顺序法较好。
    ②如需知道塔中每一点到最下层的最大值时,使用逆序法较好。

    展开全文
  • 例题1: 问题描述 假设桌子上有n根火柴,我先手取1,2,…,k(k<=n)根火柴,之后我的对手也必须取1,2,…k根火柴。双方轮换重复直到最后一根火柴被捡起来。最后一个捡起来火柴的人是输家,那么,先手在什么情况...

    例题1:

    问题描述

         假设桌子上有n根火柴,我先手取1,2,…,k(k<=n)根火柴,之后我的对手也必须取1,2,…k根火柴。双方轮换重复直到最后一根火柴被捡起来。最后一个捡起来火柴的人是输家,那么,先手在什么情况下有必胜策略呢?

          输入数据只有一行,n和k分别表示火柴总数和每次取的最大数量。

          输出数据只有一行,如果先手获胜输出win否则输出lose。

    样例输入 

    30 3

    样例输出

    win

    样例数据解释

          先手者保证火柴数量每次都取到29,25,21,17,13,9,5,1就能够达到必胜状态。

    题目分析

          对于样例数据,从最终状态分析,如果最后只有一根火柴,则当时取的人一定会输。那么如果先手面对的是5根火柴,那么无论怎么取,后手都有办法使先手操作时达到只剩下1根火柴的必输状态。同理,剩下9,13,17,…,29根火柴的时候先手的人一定会输。

          这样规律就很明显了,如果先手开局面对的不是必输态,那么先手只需要将当前局势调整为后手必输态那么先手就赢了。而调整的方法就是让场上的火柴数量处于p * (k+1) + 1, p = 1,2,…的状态。

          所以,令dp[i]表示当前场上剩余i根火柴的时候的状态,dp[i] =1表示必输态,dp[i] = 0表示必胜态,则动态规划的转移应该是 dp[i] = dp[i - k - 1], 边界条件是dp[1] = 1, dp[2] = dp[3] = …= dp[k+1] = 0;

    代码展示

    
     
    
     
     1/*
     2    example input: 30 3
     3    example output: win
     4*/
     5#include<bits/stdc++.h>
     6using namespace std;
     7int n, k;// n个火柴,每次取1..k个 
     8int *dp;
     9int main(){
    10    scanf("%d %d", &n, &k);
    11    dp = new int[n + 1];
    12    for (int i = 1; i <= n; i ++) dp[i] = 0;
    13
    14    dp[1] = 1;// 先手一根必输
    15
    16    for (int i = 1; i <= n; i += k + 1) dp[i] = 1;// 每隔k+1个出现一次必输态 
    17
    18    if (dp[n]) printf("lose\n");
    19    else printf("win\n");
    20}
    

    第一题是不是很简单呐,下面开始下一题啦

    例题2

    问题描述

          我现在有一个m-oz的杯子和一个n-oz的杯子,我妈妈要求我带回家恰好T-oz的牛奶,我应该如何实现?

          输入数据只有一行 m, n, T分别表示两个杯子的容量以及目标牛奶量(要带回家的牛奶量)。

          输出数据有若干行,最后一行是一个数字p,表示最小的操作次数,前面p行表示操作路径(倒序)

    样例输入

    9 4 6

    样例输出

    6 0

    6 4

    9 1

    0 1

    1 0

    1 4

    5 0

    5 4

    9 0

    0 0

    10

    样例数据解释

          开始有一个9-oz的杯子和一个4-oz的杯子,目标是带回家6-oz的牛奶。首先倒满9oz之后把9oz倒入4oz的杯子加满,得到一个装着5oz和4oz牛奶的杯子,然后倒掉4oz的那一杯,再把5oz的那一杯倒入4oz那一杯,再倒掉,这时9oz的杯子里面有1oz牛奶,4oz的那一个杯子是空的,把那1oz的牛奶倒入4oz杯子里面,再加满9oz的杯子,最后用9oz杯子里面的牛奶倒入4oz的杯子里面,就得到了6oz的牛奶。

    题目分析

          要用动态规划解决这个问题,首先要划清楚状态转移,一共有6种操作,8种状态。分别是倒空A杯子,倒空B杯子,倒满A杯子,倒满B杯子,用A倒满B(两种状态,A比B多或者比B少),用B倒满A(两种状态,A比B多或者比B少)

          需要注意的是,当达到某一种状态之后,之后的状态都是通过这种状态转移过来,而对于每一个子问题,都是与原问题相似的问题,因此满足子问题的重叠性。

          我们另dp[x][y]表示达到杯子A中有xoz的牛奶,B中有yoz的牛奶的状态的最小步骤,那么dp[x][y] = min(dp[i][j]) + 1, 其中i,j是所有能够推到x,y的状态。转移有了,对于边界就是初始状态下,dp[0][0] = 0.

    代码展示

    
     
      1/*
      29 4 6
      3数据保证有解 
      4*/
      5#include<bits/stdc++.h>
      6using namespace std;
      7
      8int **dp; // dp[i][j] 表示第一个杯子是i,第二个杯子是j的时候的最小步数
      9int m, n; // 表示两个杯子的容量。
     10int T; // T 为目标函数值 
     11struct arr{
     12    int x, y;
     13};
     14
     15arr make_arr(int x, int y){
     16    arr tmp;
     17    tmp.x = x;
     18    tmp.y = y;
     19    return tmp;
     20}
     21
     22bool operator <(const arr &a, const arr &b){
     23    return (a.x < b.x || (a.x == b.x && a.y < b.y));
     24}
     25
     26bool operator ==(const arr &a, const arr &b){
     27    return (a.x == b.x && a.y == b.y);
     28}
     29
     30map<arr, arr> solution;
     31
     32void dfs(int x, int y){
     33    //达到目标值 
     34    if (x == T || y == T) return;
     35
     36    //倒空B 
     37    if (dp[x][0] < 0){
     38        dp[x][0] = dp[x][y] + 1;
     39        dfs(x, 0);
     40        solution[make_arr(x, 0)] = make_arr(x, y);
     41    } 
     42
     43    //加满A 
     44    if (dp[m][y] < 0){
     45        dp[m][y] = dp[x][y] + 1;
     46        dfs(m, y);
     47        solution[make_arr(m, y)] = make_arr(x, y);
     48    }
     49
     50    //加满B
     51    if (dp[x][n] < 0){
     52        dp[x][n] = dp[x][y] + 1;
     53        dfs(x, n);
     54        solution[make_arr(x, n)] = make_arr(x, y);
     55    } 
     56
     57    //倒空A
     58    if (dp[0][y] < 0) {
     59        dp[0][y] = dp[x][y] + 1;
     60        dfs(0, y);
     61        solution[make_arr(0, y)] = make_arr(x, y);
     62    }
     63
     64    //A加入B
     65    if (x + y <= n && dp[0][x + y] < 0){
     66        dp[0][x + y] = dp[x][y] + 1;
     67        dfs(0, x + y);
     68        solution[make_arr(0, x + y)] = make_arr(x, y);
     69    } 
     70
     71    if (x + y > n && dp[x - n + y][n] < 0){
     72        dp[x - n + y][n] = dp[x][y] + 1;
     73        dfs(x - n + y, n);
     74        solution[make_arr(x - n + y, n)] = make_arr(x, y);
     75    }
     76
     77    //B加入A
     78    if (x + y <= m && dp[x + y][0] < 0){
     79        dp[x + y][0] = dp[x][y] + 1;
     80        dfs(x + y, 0);
     81        solution[make_arr(x + y, 0)] = make_arr(x, y);
     82    } 
     83
     84    if (x + y > m && dp[m][x + y - m] < 0){
     85        dp[m][x + y - m] = dp[x][y] + 1;
     86        dfs(m, x + y - m);
     87        solution[make_arr(m, x + y - m)] = make_arr(x, y);//记录路径,上同 
     88    }
     89
     90}
     91
     92
     93int main(){
     94    scanf("%d %d %d", &m, &n, &T);
     95
     96    dp = new int*[m + 1];
     97    for (int i = 0; i <= m; i ++){
     98        dp[i] = new int[n + 1];
     99        for (int j = 0; j <= n; j ++){
    100            dp[i][j] = -1;//开始不能达到 
    101        }
    102    }
    103    dp[0][0] = 0;//初始化边界条件 
    104    dfs(0, 0);// dp过程 
    105    int id_x, id_y;
    106    int ans = 0x7fffffff, ans1 = ans, ans2 = ans;
    107    if (T > m) {// 如果目标值大于第二个杯子,那么最优解在第一个杯子里面 
    108        for (int i = 0; i <= m; i ++) 
    109            if (dp[i][T] > 0 && ans1 > dp[i][T] + (int)(i > 0)) {
    110                ans1 = dp[i][T] + (i > 0);
    111                id_x = i;
    112            }
    113    }
    114    else if (T > n){//如果目标值大于第一个杯子,那么最优解在第二个杯子里面 
    115        for (int i = 0; i <= n; i ++) 
    116            if (dp[T][i] > 0 && ans2 > dp[T][i] + (int)(i > 0)) {
    117                ans2 = dp[T][i] + (i > 0);
    118                id_y = i;
    119            }
    120    }
    121    else{
    122        for (int i = 0; i <= m; i ++) 
    123            if (dp[i][T] > 0 && ans1 > dp[i][T] + (int)(i > 0)) {
    124                ans1 = dp[i][T] + (i > 0);
    125                id_x = i;
    126            }
    127        for (int i = 0; i <= n; i ++) 
    128            if (dp[T][i] > 0 && ans2 > dp[T][i] + (int)(i > 0)) {
    129                ans2 = dp[T][i] + (i > 0);
    130                id_y = i;
    131            }
    132    }//两个杯子都有可能 
    133    if (ans1 < ans2){
    134        ans = ans1 + 1;//初始00也算一步。。 
    135        printf("%d %d\n", 0, T);
    136        arr tmp = make_arr(id_x, T);
    137        while (tmp.x || tmp.y){
    138            printf("%d %d\n", tmp.x, tmp.y);
    139            tmp = solution[tmp];
    140        } 
    141        printf("%d %d\n", tmp.x, tmp.y);
    142    }else{
    143        ans = ans2 + 1;
    144        printf("%d %d\n", T, 0);
    145        arr tmp = make_arr(T, id_y);
    146        while (tmp.x || tmp.y){
    147            printf("%d %d\n", tmp.x, tmp.y);
    148            tmp = solution[tmp];
    149        } 
    150        printf("%d %d\n", tmp.x, tmp.y);//回溯找解 
    151    }
    152    printf("%d\n", ans);
    153}
    

    进入今天的最后一题了呢,想想还是有些按捺不住自己内心的激动呢!

    例题3

    问题描述

          小明住在纽约,但是他想开车(这个人为什么不坐飞机)去拉斯维加斯去追求金钱和名声。但是,众所周知,小明很穷,所以他每次都只能开到附近朋友的房子里面,然后休整一下, 准备第二天再出发。由于小明平日比较积德,所以他的朋友很多。他经过规划知道,第一天可以到某几个朋友(比如小红,小白)家,然后第二天从前日借宿的朋友家出发可以到另一组朋友中的一人的家中,如此重复几天,最终可以到达拉斯维加斯。

          现在约定,小明一共有n-2个朋友,所以包括他家以及拉斯维加斯一共有n个点,他每天可以从k_t个朋友中选择一个到达,但是到达每一家的花费不同,请问小明如何用最省钱的方式到达拉斯维加斯。

          输入数据,第一行两个整数n和m分别表示小明可以落脚的点的数量(包括自己家,朋友家,拉斯维加斯)和预算到达的天数(在自己家和拉斯维加斯都要算一天)。

           接下来m-2行中的第i行的第一个数字k_i表示第i+1天可以到达的朋友家数量,后面k_i个数表示这k_i个朋友的编号。当然,接下来一行是数字1和拉斯维加斯的编号。

    接下来n-1行,第i行有k_i+1个数字表示小明第i天的落脚点到第i+1天的落脚点之间的距离。

          输出数据, 共有两行,第一行是一个整数,表示最小花费,第二行是路程方案,用空格隔开。

          注意,数据中落脚点的编号是0..n-1并非0..n

    样例输入

    10 5

    1 0

    3 1 2 3

    3 4 5 6

    2 7 8

    1 9

    550 900 770

    680 790 1050

    580 760 660

    510 700 830

    610 790

    540 940

    790 270

    1030

    1390

    样例输出

    2870

    0 1 4 7 9

    样例解释

        样例数据中输入数据做出的图如下图3-1,依照这个图可以算出最小花费为2870,路径为0-1-4-7-9(图中编号为1,…,n,对应到图上要每个编号加一)

    题目分析

          这是一个比较简单的题目,题目中状态划分比较清楚,定义dp[i][j]表示第i阶段到达j城市的最小距离即可,很容易就能够推出动归方程dp[i][j] = min(dp[i][j], dp[i-1][k]+dis[k][j]),其中dis[k][j]表示城市k与城市j之间的距离。

    图3-1

    代码展示

    
     
    
     
      1/*
      2sample input:
      310 5
      41 0
      53 1 2 3
      63 4 5 6
      72 7 8
      81 9
      9550 900 770
     10680 790 1050
     11580 760 660
     12510 700 830
     13610 790
     14540 940
     15790 270
     161030
     171390
     18*/
     19
     20#include<bits/stdc++.h>
     21using namespace std;
     22#define INF 0x3f3f3f3f
     23
     24int **dp;// dp方程 
     25int **graph;// 从至表 
     26int N, T;// 城市数量以及阶段数量 
     27int *fa;// 记录上一个访问。 
     28typedef vector<int> List;
     29List *Nodes;// node[i]表示i的下层节点 
     30
     31void print(int x){
     32    if (x == fa[x]){
     33        printf("%d ", x);
     34        return;
     35    }else{
     36        print(fa[x]);
     37        printf("%d ", x);
     38    }
     39}
     40
     41int main(){
     42    scanf("%d %d", &N, &T);
     43
     44    dp = new int*[T];
     45    for (int i = 0; i < T; i ++){
     46        dp[i] = new int[N];
     47        for (int j = 0; j < N; j ++) dp[i][j] = INF;
     48    }//初始化 
     49
     50    Nodes = new List[T];
     51    int m, x;
     52    for (int i = 0; i < T; i ++){
     53        scanf("%d", &m);
     54        Nodes[i].clear();
     55        for (int j = 0; j < m; j ++){
     56            scanf("%d", &x);
     57            Nodes[i].push_back(x);
     58        }
     59    }// 读入每一层包含的节点编号 
     60
     61    graph = new int*[N];
     62    fa = new int[N];
     63    for (int i = 0; i < N; i ++){
     64        graph[i] = new int[N];
     65        fa[i] = i;//初始化前驱节点,方便记录路径 
     66        for (int j = 0; j < N; j ++){
     67            graph[i][j] = INF;
     68        }
     69    }// 初始化输入输出 
     70
     71    for (int i = 0; i < T - 1; i ++){
     72        int sz_1 = Nodes[i].size(), sz_2 = Nodes[i + 1].size();
     73        for (int j = 0; j < sz_1; j ++){
     74            for (int k = 0; k < sz_2; k ++){
     75                scanf("%d", &graph[Nodes[i][j]][Nodes[i + 1][k]]);
     76            }
     77        }
     78    }// 读入每一层结点与下层节点之间的距离
     79
     80    for (int i = 0; i < Nodes[0].size(); i ++) dp[0][Nodes[0][i]] = 0;// 初始化边界,到达出发点花费为0
     81    for (int i = 1; i < T; i ++){
     82        int sz_1 = Nodes[i].size(), sz_2 = Nodes[i - 1].size();
     83        for (int j = 0; j < sz_1; j ++){
     84            int x = Nodes[i][j];
     85            for (int k = 0; k < sz_2; k ++){
     86                int y = Nodes[i - 1][k];
     87                //dp[i][x] = min(dp[i][x], dp[i - 1][y] + graph[y][x]);
     88                if (dp[i][x] > dp[i - 1][y] + graph[y][x]){
     89                    dp[i][x] = dp[i - 1][y] + graph[y][x];// 更新dp方程 
     90                    fa[x] = y;// 记录路径 
     91                }
     92            }
     93        }
     94    }
     95    for (int i = 0; i < Nodes[T - 1].size(); i ++){
     96        printf("%d\n", dp[T - 1][Nodes[T - 1][i]]);
     97        int x = Nodes[T - 1][i];
     98        print(x);
     99        printf("\n");
    100    }// 输出路径以及结果 
    101}
    展开全文
  • C++ 动态规划例题详解

    千次阅读 2019-04-17 19:59:16
    递推问题 利用递推解决问题,我们就要模仿求斐波那契数列的过程。首先,确定几个规模较小的问题答案。然后考虑如何由这几个...例题1: 代码: // // 93.cpp // N阶楼梯上楼问题 // // Created by chenmeiqi on...

    递推问题

    利用递推解决问题,我们就要模仿求斐波那契数列的过程。首先,确定几个规模较小的问题答案。然后考虑如何由这几个规模较小的答案推得后面的答案。一旦有了递推规则和数列初始的几个值,计算机程序就能帮助我们求解数列后面的所有数字,我们的问题也得到了解决。

    例题1:

    代码:

    //
    //  93.cpp
    //  N阶楼梯上楼问题
    //
    //  Created by chenmeiqi on 2019/4/17.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    // 递归解法
    int getKind(int n){
        if(n==1) return 1;
        else if(n==2) return 2;
        else {
            return getKind(n-1)+getKind(n-2);
        }
    }
    int main(int argc, const char * argv[]) {
        int n;
        long long res[90];          // res数组保存数列的每一个值,由于数值过大,我们需要使用long long类型
        while (cin>>n) {
    //        cout<<getKind(n)<<endl;           // 递归解法
            res[1]=1;
            res[2]=2;
            for (int i=3; i<=n; i++) {
                res[i]=res[i-1]+res[i-2];
            }
            cout<<res[n]<<endl;
        }
        return 0;
    }
    

    分析: 


    例题2:

     代码:

    //
    //  94.cpp
    //  不容易系列之一
    //
    //  Created by chenmeiqi on 2019/4/17.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    int getKinds(int n){
        if(n==1){
            return 0;
        }
        else if(n==2){
            return 1;
        }
        else{
            return (n-1)*getKinds(n-1)+(n-1)*getKinds(n-2);
        }
    }
    int main(int argc, const char * argv[]) {
        int n;
        while (cin>>n) {
            cout<<getKinds(n)<<endl;
        }
        return 0;
    }
    

    分析:(错排公式) 


    最长递增子序列(LIS)

    例题:

    代码:

    //
    //  95.cpp
    //  拦截导弹
    //
    //  Created by chenmeiqi on 2019/4/17.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    #include <algorithm>
    using namespace std;
    bool cmp(int a,int b){      // 从高到低排
        return a>b;
    }
    int main(int argc, const char * argv[]) {
        int k;
        int a[26];
        int max;
        while (cin>>k) {
            int res[26]={0};                    // 初始化,便于排序
            for (int i=0; i<k; i++) {
                cin>>a[i];
            }
            res[0]=1;               //  初始化0位置的最长子序列为1
            for (int i=1; i<k; i++) {
                res[i]=1;
                max=1;
                for (int j=i-1; j>=0; j--) {
                    if (a[i]<=a[j] && res[j]+1>max) {      // “不高于”
                        res[i]=res[j]+1;
                        max=res[i];
                    }
                }
            }
            sort(res, res+26,cmp);          // 排序
            cout<<res[0]<<endl;
        }
        return 0;
    }
    

     分析:


    最长公共子序列(LCS)

    例题:

    代码:

    //
    //  98.cpp
    //  Coincidence
    //
    //  Created by chenmeiqi on 2019/4/28.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    
    using namespace std;
    
    int main(int argc, const char * argv[]) {
        string n,m;
        int res[101][101];
        size_t n_len,m_len;
        while (cin>>n>>m) {
            n=' '+n;            // 方便设置初始值和下标
            m=' '+m;
            n_len=n.length();
            m_len=m.length();
            for (int i=0; i<n_len; i++) {       // 二重循环依次求得每个dp[i][j]的值
                for (int j=0; j<m_len; j++) {
                    if (i==0||j==0) {               // 初始值
                        res[i][j]=0;
                    }
                    else if(n[i]==m[j]){        // 若当前两字符相等
                        res[i][j]=res[i-1][j-1]+1;
                    }
                    else{       // 若不相等
                        res[i][j]=max(res[i-1][j], res[i][j-1]);
                    }
                }
            }
            cout<<res[n_len-1][m_len-1]<<endl;
        }
        return 0;
    }
    

    分析:


    状态与状态转移

    题目:

    代码:

    //
    //  99.cpp
    //  搬寝室
    //
    //  Created by chenmeiqi on 2019/4/28.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    #define INF 0xfffffff    // 预定义最大的int取值为无穷
    int main(int argc, const char * argv[]) {
        int n,k;
        int w[2001];        // 保存每个物品重量
        int  dp[1001][2001];        // 保存每个状态
        while (cin>>n>>k) {
            w[0]=0;
            for (int i=1; i<=n; i++) {
                cin>>w[i];
            }
            sort(w+1, w+1+n);       // 使所有物品按照重量递增排序
            for (int i=0; i<=k; i++) {
                for (int j=0; j<=n; j++) {
                    if (i==0) {       // 初始值
                        dp[i][j]=0;
                    }
                    else if(2*i>j){     // 配对数大于总数,设置为正无穷
                        dp[i][j]=INF;
                    }
                    
                    else{       // 根据最后一个是否配对分为两种情况,取最小值
                        dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(w[j]-w[j-1])*(w[j]-w[j-1]));
                    }
                }
            }
            cout<<dp[k][n]<<endl;
        }
        return 0;
    }
    

    分析:

     


    双塔dp

    题目:

     代码:

    //
    //  100.cpp
    //  Greedy Tino
    //
    //  Created by chenmeiqi on 2019/4/28.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    #define OFFSET 2000     // 因为柑橘重量差存在负数的情况,即第一堆比第二堆轻,所以在计算重量差对应的数组下标时应加上该偏移值,使每个重量差对应合法的数组下标
    #define INF 0x7ffffff       // 无穷
    int w[101];     // 保存柑橘数量
    int dp[101][4001];      // 保存状态
    int main(int argc, const char * argv[]) {
        int t,n;
        cin>>t;
        for (int s=1; s<=t; s++) {
            bool hasZero=false;     //统计是否存在重量为0的柑橘
            int count=1;        // 计数器,记录共有多少个重量非零的柑橘
            cin>>n;
            for (int i=1; i<=n; i++) {      // 输入n个柑橘重量
                cin>>w[count];
                if(w[count]==0){            // 若当前输入柑橘重量为0
                    count--;        // 去除这个柑橘
                    hasZero=true;       // 并记录:存在重量为0的柑橘
                }
                count++;
            }
            count--;            // 要-1
            n=count;
            for (int i=-2000; i<=2000; i++) {
                dp[0][i+OFFSET]=-INF;           // 初始化,不往两堆中加任何柑橘时,两堆重量差不为0的状态不存在
            }
            dp[0][0+OFFSET]=0;          //  不往两堆中加任何柑橘时,两堆最大总重量为0
            for (int i=1; i<=n;i++) {       // 遍历每个柑橘
                for (int j=-2000; j<=2000; j++) {       // 遍历每种可能的重量差
                    int tmp1=-INF,tmp2=-INF;            // 分别记录当前柑橘放在第一堆获第二堆时转移得来的新值,若无法转移则为-INF
                    if(j+w[i]<=2000 && dp[i-1][j+w[i]+OFFSET]!=-INF){       // 当状态可由第一堆转移而来时(放到第二堆)
                        tmp1=dp[i-1][j+w[i]+OFFSET]+w[i];           // 记录转移值
                    }
                    if(j-w[i]>=-2000 && dp[i-1][j-w[i]+OFFSET]!=-INF){      // 当状态可由第二堆转移而来时(放到第一堆)
                        tmp2=dp[i-1][j-w[i]+OFFSET]+w[i];
                    }
                    if(tmp1<tmp2){          // 取较大的那个,存到tmp1
                        tmp1=tmp2;
                    }
                    if(tmp1<dp[i-1][j+OFFSET]){     //将tmp1与当前柑橘不放入任何堆,即状态差不发生改变的原状态值比较,取较大的那个,存到tmp1
                        tmp1=dp[i-1][j+OFFSET];
                    }
                    dp[i][j+OFFSET]=tmp1;       // 当前状态值
                }
            }
            if (dp[n][0+OFFSET]==0) {           // 不存在任何非0的组合使两堆重量相等
                if(hasZero){
                    cout<<"Case "<<s<<":"<<0<<endl;             // 存在重量为0的柑橘
                }
                else{
                    cout<<"Case "<<s<<":"<<-1<<endl;        // 不存在
                }
            }
            else{
                cout<<"Case "<<s<<":"<<dp[n][0+OFFSET]/2<<endl;     // 直接输出
            }
        }
        return 0;
    }
    

    分析:


    背包问题 

    0-1背包

    代码:

    //
    //  101.cpp
    //  采药
    //
    //  Created by chenmeiqi on 2019/5/2.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    struct N{           // 保存物品信息结构体
        int t;      // 物品体积(采摘时间)
        int w;      // 物品价值
    };
    //int main(int argc, const char * argv[]) {
    //    int T,M;
    //    N herb[101];
    //    int time;
    //    int dp[101][1001];        // 记录状态数组,dp[i][j]表示前i个物品组成的总体积不大于j的最大价值和
    //    while (cin>>T>>M) {
    //        time=0;
    //        for (int i=1; i<=M; i++) {        // 输入
    //            cin>>herb[i].t>>herb[i].w;
    //        }
    //        for (int i=0; i<=M; i++) {            // 初始化状态
    //            dp[0][i]=0;
    //        }
    //        for (int i=1; i<=M; i++) {        // 循环每一个物品
    //            for (int j=T; j>=herb[i].t; j--) {        // 对T到herb[i].t的每个j,状态转移来源为dp[i-1][j]或dp[i-1][j-herb[i].t]+herb[w],选择其中较大的值
    //                dp[i][j]=max(dp[i-1][j-herb[i].t]+herb[i].w,dp[i-1][j]);
    //            }
    //            for (int j=herb[i].t-1; j>=0; j--) {      // 对herb[i].t-1到0的每个j,状态仅能来源于dp[i-1][j],固直接赋值
    //                dp[i][j]=dp[i-1][j];
    //            }
    //        }
    //        cout<<dp[M][T]<<endl;
    //    }
    //    return 0;
    //}
    int main(int argc, const char * argv[]) {
        int T,M;
        N herb[101];
        int time;
        int dp[101];
        while (cin>>T>>M) {
            time=0;
            for (int i=1; i<=M; i++) {
                cin>>herb[i].t>>herb[i].w;
            }
            for (int i=0; i<=M; i++) {
                dp[i]=0;
            }
            for (int i=1; i<=M; i++) {
                for (int j=T; j>=herb[i].t; j--) {      // 必须倒序更新每个dp[j]的值,j小于herb[i].t的各dp[j]不更新,保持原值,即等价于dp[i][j]=dp[i-1][j]
                    dp[j]=max(dp[j],dp[j-herb[i].t]+herb[i].w);     // dp[j]在原值和dp[j-list[i].w]+list[i].v中选取较大的那个
                }
            }
            cout<<dp[T]<<endl;
        }
        return 0;
    }
    


    完全背包

    代码:

    //
    //  102.cpp
    //  Piggy-Bank
    //
    //  Created by chenmeiqi on 2019/5/2.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    #define INF 0x7fffffff
    
    struct N{           // 代表钱币结构体
        int w;
        int v;
    }list[501];
    
    int main(int argc, const char * argv[]) {
        int T,E,F,N;
        int dp[10001];
        cin>>T;
        while (T--) {
            cin>>E>>F;
            cin>>N;
            int s=F-E;
            for (int i=1; i<=N; i++) {
                cin>>list[i].v>>list[i].w;
            }
            dp[0]=0;
            for (int i=1; i<=s; i++) {      // 初始化与 0-1 bag 不同。(要求恰好装满)
                dp[i]=INF;
            }
            for (int i=1; i<=N; i++) {
                for (int j=list[i].w; j<=s; j++) {      // 顺序遍历
                    if (dp[j-list[i].w]!=INF) {         // 若dp[j-list[i].w]不为无穷,就可以由o此状态转移而来
                        dp[j]=min(dp[j],dp[j-list[i].w]+list[i].v);     // 取最小值
                    }
                }
            }
            if (dp[s]!=INF) {       // 存在一种方案使背包恰好装满。输出其最小值
                 cout<<"The minimum amount of money in the piggy-bank is "<<dp[s]<<endl;
            }
            else{       // 不存在
                cout<<"This is impossible"<<endl;
            }
        }
        return 0;
    }
    

    分析:


    多重背包

    题目

    代码:

    //
    //  103.cpp
    //  珍惜现在,感恩生活
    //
    //  Created by chenmeiqi on 2019/5/4.
    //  Copyright © 2019年 chenmeiqi. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    
    struct N{       // 大米
        int v;      // 价格
        int w;      // 重量
    }list[2001];   // 100*20
    
    int main(int argc, const char * argv[]) {
        int C;
        int n,m;
        int count;
        int  dp[101];
        cin>>C;
        while (C--) {
            count=0;            // 拆分后物品总数
            cin>>n>>m;
            for (int i=1; i<=m; i++) {      // 输入
                int v,w,k;
                cin>>v>>w>>k;
                int c=1;
                while (k-c>0) {         // 对输入的数字k,拆分成1,2,4...k-2^c-1
                    k-=c;
                    list[++count].v=v*c;            // 拆分后的大米重量和价格均为组成该物品的大米的重量价格和
                    list[count].w=w*c;
                    c*=2;
                }
                list[++count].v=v*k;
                list[count].w=w*k;
            }
            for (int i=1; i<=n; i++) {      // 初始值
                dp[i]=0;
            }
            for(int i=1;i<=count;i++){          // 对拆分后的所有物品进行0-1背包
                for (int j=n; j>=list[i].v; j--) {
                    dp[j]=max(dp[j], dp[j-list[i].v]+list[i].w);
                }
            }
            cout<<dp[n]<<endl;
        }
        return 0;
    }
    

    分析:

    展开全文
  • 动态规划经典例题

    千次阅读 2015-11-02 20:02:30
    关于动态规划的介绍很多,本文希望通过重复几个最经典的例题来理解动态规划。 问题1 求一个字符串中的最长的回文子串 回文是指正着读和倒着读,结果一样,比如abcba或abba。 分析: 令状态方程p[i][j]=0表示起始...
  • 竞赛算法–动态规划 例题详解 动态规划方法代表了这一类问题(最优子结构or子问题最优性)的一般解法,是设计方法或策略,不是具体算法 本质是递推,核心是找到状态转移方程,写出DP方程。 形式: ...
  • 自低而上的分析,每次累加新的常量,中间只能相隔两个或者一个字符,dp[i]的值取决于dp[i-2]和i的和,还有dp[i-1]的大小。 dp [ 0 ] = nums [ 0 ] ; dp [ 1 ] = max ( nums [ 1 ] , nums [ 0 ] ) ; ...
  • c动态规划精简例题

    2020-11-23 17:23:48
    c动态规划精简例题 1. 单序列型 爬楼梯 //1.爬楼梯 int minCostClimbingStairs(int cost[], int n) { int dp[n]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < n; i++) { dp[i] = min{dp[i -...
  • 算法分析与设计 动态规划 解决最长公共子序列问题
  • 矩阵取数问题分析:代码:例题2:2.最大字段和问题代码:例题3:[3.最长公共子序列]例题4:4.编辑距离例题5:5.最长递增子序列 简单介绍 动态规划(dynamic programming),简称DP。是运筹学的一个分支,我们不会学的...
  • #闫氏dp分析法 ->dp问题     首先是在看问题时,知道这道题要用dp去做,但是怎么去实现呢?空想是很难去构造式子的,闫氏dp方法的核心就是用集合的方法去分析问题,从集合的角度入手去解决...
  • 【算法竞赛入门经典】DAG上的动态规划 例题9-1 UVa1025 【算法竞赛入门经典】DAG上的动态规划 例题9-1 UVa1025 例题UVa1025 分析 样例实现代码 结果 例题UVa1025 Secret agent Maria was sent to ...
  • 【算法竞赛入门经典】递归结构的动态规划 例题9-10 UVa1626 【算法竞赛入门经典】递归结构的动态规划 例题9-10 UVa1626 例题UVa1626 分析 样例实现代码 结果 例题UVa1626 Let us define a regular ...
  • 【算法竞赛入门经典】DAG上的动态规划 例题9-3 UVa1347 【算法竞赛入门经典】DAG上的动态规划 例题9-3 UVa1347 例题UVa1347 分析 样例实现代码 结果 例题UVa1347 John Doe, a skilled pilot, enjoys ...
  • 【算法竞赛入门经典】DAG上的动态规划 例题9-2 UVa437 【算法竞赛入门经典】DAG上的动态规划 例题9-2 UVa437 例题UVa437 分析 样例实现代码 结果 例题UVa437 Perhaps you have heard of the legend of ...
  • 动态规划可能是算法里边最难的,也可能是机试里最难的,所以作为小白,最好是能积累,丰富自己的题库,以下是我在刷保/考研究生机试题的动态规划的内容,都比较简答,以后遇到类似题目还会不断更新。 感谢计算机...
  • 动态规划及相关例题

    2020-09-01 19:05:39
    动态规划及相关例题 一、定义 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。动态规划与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),...
  • 算法设计与分析例题

    千次阅读 2012-09-26 17:48:17
    //模仿人工的大整数加法 int add(int m,int a[],int n,int b[],int c[]) { int i,k,p,q;  if(m>n){k=m;for(i=n;i  else{k=n;for(i=m;i  p=0; for(i=0;i  if(p){c[k]=p;...//采用分治策略的
  • 为啥要使用动态规划?什么时候使用动态规划?以下是我的一些理解和心得,如果你感兴趣,就接着往下看吧。 对您有帮助的话记得给我点个赞哟! 动态规划的基本思想 动态规划(Dynamic Programming,DP)算法通常用于...
  • 动态规划典型例题解析

    千次阅读 2018-12-20 23:09:08
    什么是动态规划 动态规划的主要思想就是把问题划分为一个个子状态,一个状态的最优解往往是基于其前一个的状态的最优解。两个状态之间的关系,我们就称之为状态转移方程。这里引出了状态和状态转移方程的概念:状态...
  • 分析:从第一行开始从左向右查找 对于物品3,容量4 要该物品:f(3,4) = 物品价值+f(物品3的上一个物品2,容量4-物品重量); 不要该物品:f(3,4) = f(物品3的上一个物品,容量4) 最后取max(要f,不要f) 代码: ...
  • 4 动态规划算法的基本要素 一最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质 在分析问题的最优子结构性质时所用的方法具有普遍性首先假设由问题的最优解导出的子问题的...
  • 动态规划算法典型例题

    千次阅读 多人点赞 2020-05-02 12:08:07
    1. 动态规划之选数问题 题目要求: 假设给定一串数字{1, 2, 4, 1, 7, 8, 3},我们要从中选择若干个数,使最后的和达到最大。选择的规则是,不能选相邻的数字。比如:如果我们选了第一个数字1,那么我们就不能选2,...
  • 合并石子-动态规划经典例题【问题描述】【输入格式】【输入样例】【输出样例】【算法分析】【源代码】 【问题描述】 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,673
精华内容 3,469
关键字:

动态分析例题