当前位置:   article > 正文

算法学习 - 动态规划(DP问题)装配线问题(C++)_装配线问题c++

装配线问题c++

这几天一直再看,觉得看懂了一些,先记下来。

1. 动态规划

动态规划是运筹学的一个方向,就是把多级最优化问题分解成一系列的单阶问题。在不断增加的过程中,不断的计算当前问题的最优解。

一般分为如下四个部分:

  • 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;
  • 区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;
  • 树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;
  • 背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

2. 汽车生产线问题

这个问题是《算法导论》的动态规划的例题,我自己觉得这道题比较简单而且典型,所以就解释下这个题目:

Colonel汽车公司在有两条装配线的工厂里生成汽车。每一条装配线上有n个装配站,两条生产线上相同位置的装配站功能相同,但所需时间不同,并且汽车底盘在两条装配线间转移要花费一定的时间。如下图所示两条生产线。

装配线图

  1. 首先我们知道每个阶段的最短时间,都包含了上一阶段的最短时间。

  2. 而比较简单的是,我们只有两种情况,一种是在装配线1上时间短,一种是在装配线2上时间短。

  3. 假如暴力搜索,贪心去算得话(也就是递归的办法)。时间复杂就是2^n,这个是不可接受的。

这个时候我们的办法是先从第一个问题开始,装配线1, 2上只有一个station。那么比较简单,一比较就好了。当有两个station的时候,就是从上一次比较的结果中(一个line 1最短,一个line 2最短)中继续加上当前station的值继续比较。

所以我们发现是每个当前的最优解,都包含了上一次的最优解。

3. 代码

代码就是我们从最开始,一直保存当前问题的最优解,然后去求的下一次的最优解。

//
//  main.cpp
//  DP_line
//
//  Created by Alps on 15/4/26.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include <iostream>
using namespace std;

#define NUM 5

int main(){
    int first[NUM];//到装备站1,i的最短路径长度
    int second[NUM];//到装配站2,i的最短路径长度
    int linef[NUM]; //从1进入的路径
    int lines[NUM]; //从2进入的路径
    int a[NUM]; //在装配站1,i 所需要呆的时间
    int b[NUM]; //再装配站2,i 所需要呆的时间
    int m[NUM]; //从装配站1,i-1 到装配站2,i的时间
    int n[NUM]; //从装配站2,i-1 到装配站1,i的时间
    int line[NUM]; //当前最短路经所经过的装配站
    int f[NUM]; //当前最短路径长度
    int ea,eb,xa,xb; // ea为进入装配站1时间,eb为进入2的时间,xa为出装配站1的时间,xb为出装配站2的

    scanf("%d %d %d %d",&ea,&eb,&xa,&xb);
    for(int i=0;i<NUM;++i)
    {
        scanf("%d %d", &a[i], &b[i]);
    }
    first[0] = ea + a[0];
    second[0] = eb + b[0];
    for(int i=0;i<NUM-1;++i)
    {
        scanf("%d %d", &m[i], &n[i]);
    }
    for(int i=1;i<NUM;++i)
    {
        if(first[i-1] + a[i] < second[i-1] + m[i-1] + a[i])
        {
            first[i] = first[i-1] + a[i];
            linef[i] = 1;
        }else{
            first[i] = second[i-1] + m[i-1] + a[i];
            linef[i] = 2;
        }
        if(second[i-1] + b[i] < first[i-1] + n[i-1] + b[i])
        {
            second[i] = second[i-1] + b[i];
            lines[i] = 2;
        }else
        {
            second[i] = first[i-1] + n[i-1] + b[i-1];
            lines[i] = 1;
        }
    }
    for(int i=0;i<NUM;++i)
    {
        if(first[i] + xa < second[i] + xb)
        {
            f[i] = first[i] + xa;
            line[i] = 1;
        }else{
            f[i] = second[i] + xb;
            line[i] = 2;
        }
    }

    for(int i=0;i<NUM;++i)
    {
        printf("station %d\n",line[i]);
    }
    printf("Distince is %d\n",f[NUM-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
  • 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
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

这个代码比较简单,精华就是那个for循环了。

测试用例如下:

3 2 3 4
4 3
3 6
6 3
2 3
5 2
2 3
2 4
3 4
4 3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

假如有任何建议,欢迎评论。互相学习。谢谢。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/690246
推荐阅读
相关标签
  

闽ICP备14008679号