蚁群算法求解有时间窗约束的车辆路径问题matlab程序
 
1 简介
 
带时间窗的车辆路径问题(VRPTW)一般描述为从某一物流配送中心出发，用多台车辆向多个顾客送货，车辆完成配送任务后返回配送中心。 已知每个顾客的位置与需求量， 每台车的容量一定， 将货物送到顾客手中需要满足一定的时间约束， 要求合理安排行车路线使目标函数得到优化。 对该问题的研究引起了广大学者的关注。 它是有容量约束车辆路径问题的扩展， 是NP难题， 求解算法可分为精确算法与启发式算法。当顾客点数目较多时， 使用精确算法很难在可接受的时间内求得全局最优解， 因此， 用启发式算法在可接受的时间内求得问题的满意解成为研究的重要方向。
 
蚁群算法是由Dorigo等首先提出来的， 它的基本思想是利用一群人工蚂蚁的协作来寻找优化问题的较优解， 每只蚂蚁根据问题所给的准则， 从被选中的初始状态出发建立一个可行解或部分解， 各个蚂蚁间通过信息素交换信息， 从而达到相互协作的目的。蚁群算法的思想已被应用到各个研究领域， 并取得了大量的研究成果， 而在VRPTW方面的研究则较少。
 
2 有时间窗的车辆路径问题
 
为简化问题的描述，需要在构建模型前做一些基本的假设和约束:
 
    (1) 假设物流运输车辆状况相同；
 
    (2) 单车运载力要大于单个客户需求量，且每条路线上的客户需求总量不大于单车最大运载力；
 
    (3) 配送中心能够满足所有客户需求，无缺货；
 
    (4) 车辆完成配送后直接返回配送中心；
 
(5) 每条路径长度不超过单车最大行程；
 
(6) 车辆要在时间窗内到达相应客户点，否则会产生惩罚成本；
 
 
 
向客户配送货物有时间限制，在此采用软时间窗的限制方法进行处理， 即对客户需求的货物在一定的时间范围内到达，若未能按时到达，则将对物流配送企业给予一定的罚金。则因不在时间窗内将产品送到客户点而产生的处罚成本用C5表示，公式如下所示：
 
    
 
其中：分别表示车辆早于和晚于时间窗将货物卸下而带来的损失成本。为车辆到达客户 j 的时刻，为车辆在客户 j 处等待的时间。
 
3 问题求解
 
蚁群算法（Ant Colony Algorithm）可以很好地解决 VRP，因为该算法在满足各需求点的时间窗约束的前提下采用动态信息策略， 以保证在每次搜索中每只蚂蚁都对搜索做出贡献， 
 
最快地找到最优解或满意解。简单来说，此算法是一种源于自然界中生物世界新的仿生类随机型、智能多主体搜索算法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的路径优化问题求解中取得了成效。所以本文打算通过 MATLAB 强大的计算功能编写蚁群算法程序来深入研究冷链物流路径优化问题。
 
基本蚁群算法的思路如下：
 
Begin
 
初始化：
 
Nc    0;（Nc为迭代次数）
 
对各边弧（i,j）;
 
        常数c;（较小的正数）    0;
 
     Ca    L;（ca为车辆的剩余载重量）
 
     Cb    N;（Cb为车辆的剩余行驶距离）
 
 读入其他输入参数;
 
 Loop:
 
     将初始点放入当前的解集中;
 
     While（不满足停机准则）do
 
     begin
 
     对每只蚂蚁k;
 
         按照剩余载重量，剩余行驶路径长和转移概率选择顶点j;
 
         将蚂蚁k从顶点i转移到顶点j;
 
         将顶点i放在当前的解集中;
 
     end
 
     当所有的城市都放在解集中，就记录蚂蚁的个数M    k;
 
     利用局部搜索机制来优化路径;
 
     然后计算每只蚂蚁的目标函数值;
 
     并计算当前的最好解;
 
     For k   1toM do
 
     begin
 
         对各边（i,j）,计算：;（增加的信息素）
 
     end
 
         对各边（i,j）,计算：;（轨迹更新）
 
         对各边（i,j）,置;
 
         ;
 
         若Nc<预定的迭代次数，则go to Loop;
 
     End 
 
 
部分程序
%     Author:    怡宝2号			博士猿工作室
%     Use:       用蚁群算法求解有容量限制、时间窗限制的车辆路径问题；
%                坐标视自己的具体情况而定。
%     Illustrate:输入变量（must）：     
%                              coordinate：要求的相应点的坐标，第一行是点的横坐标，第二行是点的纵坐标
%                                demand（1*n），n表示工厂的个数；t表示各个工厂要求运送的货物的重量
%                                LimitW:每辆车限制的载重量
%       Can—changed parameter： m：蚁群的规模
%                                MAXGEN：蚁群的最大迭代代数
%                               
%                  输出：        bestpop：最短路程对应的路径
%                                trace ：最短路程
%				  remark：    如有疑问请咨询qq：778961303
clc
clear all
close all
format compact

%蚁群参数初始化
Alpha = 1;        %求解选择下一个城市的概率
Beta = 5;         %求解选择下一个城市的概率
Rho = 0.75;       %信息素的全局更新
Q = 200;          %信息素增加强度系数
Elite = 1;        %精英蚂蚁数量

m = 40;           %每一代有40只蚂蚁
MAXGEN = 100;     %最大迭代代数
Prab = 0.05;      %伪随机选择概率

%读取初始数据，初始化成本函数的参数
[F,C,P,ZETA1,ZETA2,THETA,R,S,ELTAT,COSTP,V,BETA,OMEGA1,OMEGA2,coordinate,demand,ET,LT,ST,speed, LimitW] = initial();          

%求各个客户点之间的距离
[Distance n] = CalculateD(coordinate);      %n为客户数量，包括配送中心

Eta=1./Distance;        %Eta为启发因子，离散模型设为距离的倒数
Tau=ones(n,n);          %Tau为信息素矩阵，行：前一个城市的标号；列：后一个城市的标号。
Tabu=zeros(m,n+20);     %存储并记录路径的生成

bestpop = zeros(MAXGEN,n+20);       %每代最优的蚂蚁
trace = zeros(MAXGEN,1);            %每代最小的成本

%迭代寻优开始开始
load = 0;               %初始化载重
NC=1;                   %迭代计数器 
while NC<=MAXGEN
    
    Tabu(:,1)=1;        %每只蚂蚁都是从仓库（及节点1）开始出发
    
    %精英保留策略
    start = 1;
    if 2<=NC
        start = Elite + 1;
    end
    
    for i=start:m
        visited=Tabu(i,:);
        visited=visited(visited>0);
        to_visit=setdiff(1:n,visited);         %在集合论中，to_visit = (1:n) - visited
        
        actualST = zeros(n,1);                 %实际服务时间，初始化，一只蚂蚁初始化一次
        actualST(1) = ET(1);                   %对初始点的服务时间，初始化
        j=1;
        while j<=n
            if ~isempty(to_visit)              %判断所有客户点是否送完
                %计算接下来要参观的其他城市的概率
                for k=1:length(to_visit)
                    [Tij actualST] = CalculateT( visited(end) , to_visit(k) ,actualST,Distance,ST,speed);            %计算从客户i到达客户j的时间
                    VC = CalculateVC( visited(end) , to_visit , actualST , Distance , ST, speed, LT);                 %计算从客户i到下一个客户的潜在客户
                    x(k)=(Tau(visited(end),to_visit(k))^Alpha)*(Eta(visited(end),to_visit(k))^Beta)*...
                         1/( abs(Tij-ET(to_visit(k))) + abs(Tij-LT(to_visit(k))) )*VC;
                end
                
                %伪随机选择，选择下一个城市
                temp_pra=rand;
                if temp_pra<Prab                %如果满足伪随机选择概率，直接选择概率最大的，这样收敛更快
                    Select=find(max(x));
                else
                    x=x/(sum(x));               %用轮盘赌法选择下一个城市
                    xcum=cumsum(x); 
                    Select=find(xcum>=rand);
                end                
                
                %计算车的载重
                if isempty(Select)              %如果选不了下一个城市了，就回到1点
                    Select=1;
                    load=load+demand(Select);   %select=1；t（select）=0
                else
                    load=load+demand(to_visit(Select(1)));       %select表示城市标号，to_visit(select)才表示城市
                end
                
                %判断载重是否超限，并对路径表修改
                if load>W                  %判断车是否超载，超载就回到原地
                    Select=1;
                    j=j-1;                      %j表示参观了的城市，参观的城市-1
                    load=0;                     %车辆的载重归零
                    Tabu(i,length(visited)+1)=Select(1);      %给车辆的路径信息赋值，及回到原点，要参观的客户赋值为1.
                else
                    Tabu(i,length(visited)+1)=to_visit(Select(1));
                end
                
            end
            
            %对访问过的客户，和待访问的客户初始化
            visited=Tabu(i,:);
            visited=visited(visited>0);                  %已经拜访过的客户
            to_visit=setdiff(1:n,visited);
            x=[];
            if visited(end)~=1
                Tabu(i,1:(length(visited)+1))=[visited,1];
            end
            j = j+1;
            j;
        end
        %1只蚂蚁配送路线完成
        load = 0;
    end
    %m只蚂蚁路线安排完成
    
    %计算m只蚂蚁的个体适应度
    L=zeros(m,1);               %共有m只蚂蚁
    for i=1:m 
        temp=Tabu(i,:); 
        route=temp(temp>0);     %每只蚂蚁的路径
    end
    
    %精英保留策略
    [ex index] = sort(L,'ascend');
    index = index(1:Elite);
    temp = Tabu(index,:);
    tempL = L(index);
    Tabu(1:Elite,:) = temp;
    L(1:Elite) = tempL;
    
    [mintrace index] = min(L);  %最小的成本
    temp = Tabu(index(1),:);    %最小成本对应的蚂蚁
    trace(NC) = mintrace;       %保存每代的最小成本和最小蚂蚁
    bestpop(NC,:) = temp;
    
    %更新信息素
    Delta_Tau=zeros(n,n);
    for i=1:m
        temp=Tabu(i,:); 
        route=temp(temp>0);
        for j=1:(length(route)-1) 
            Delta_Tau(route(j),route(j+1))=Delta_Tau(route(j),route(j+1))+Q/L(i);
        end
        Delta_Tau(route(n),route(1))=Delta_Tau(route(n),route(1))+Q/L(i);
    end
%     %信息素更新
%     Delta_Tau=zeros(n,n); 
%     for i=1:m 
%         temp=Tabu(i,:); 
%         route=temp(temp>0);
%         for j=1:(length(route)-1) 
%             Delta_Tau(route(j),route(j+1))=Delta_Tau(route(j),route(j+1))+Q/L(i);
%         end
%     end
%     Tau=(1-Rho).*Tau+Delta_Tau;
    
    %路径清零，载荷清零
    temp=zeros(m-Elite,n+20); 
    Tabu(Elite+1:m,:) = temp;
    load=0;    
    
    disp(['共迭代',num2str(MAXGEN),'次,现在为：',num2str(NC)]);
%     NC
    NC = NC + 1;
end

%绘制寻优迭代图
figure()
plot(trace)
plot(trace,'--b',...
    'LineWidth',2);
grid off
xlabel('迭代次数数')
ylabel('成本')
title('成本变化','fontsize',16)

%显示路径
[mintrace index] = min(trace);              %最小成本
route = bestpop(index,:);                   %最小成本的路径
route = route( route>0 );
p=num2str(route(1));
for i=2:length(route)
    p=[p,'->',num2str(route(i))];
end
display(['求解的最优路径为：',num2str(p)]);
display(['1代表物流中心']);
disp(['最小的成本代价为：',num2str(min(trace))]);

%绘制最小成本的路径
figure();
DrawRoute(coordinate,route)

%				  remark：    如有疑问请咨询qq：778961303

 
结果 
 

 
 

 
 

 
 

 

 
 

  
期末了，通过写博客的方式复习一下dp，把自己理解的dp思想通过样例全部说出来
  
说说我所理解的dp思想
  
dp一般用于解决多阶段决策问题，即每个阶段都要做一个决策，全部的决策是一个决策序列，要你求一个
  
最好的决策序列使得这个问题有最优解
  
将待求解的问题分为若干个相互联系的子问题，只在第一次遇到的时候求解，然后将这个子问题的答案保存
  
下来，下次又遇到的时候直接拿过来用即可
  


  
dp和分治的不同之处在于分治分解而成的子问题必须没有联系（有联系的话就包含大量重复的子问题，那
  
么这个问题就不适宜分治，虽然分治也能解决，但是时间复杂度太大，不划算），所以用dp的问题和用分
  
治的问题的根本区别在于分解成的子问题之间有没有联系，这些子问题有没有重叠，即有没有重复子问题
  


  
dp和贪心的不同之处在于每一次的贪心都是做出不可撤回的决策（即每次局部最优），而在dp中还有考察
  
每个最优决策子序列中是否包含最优决策子序列，即是否具有最优子结构性质，贪心中每一步都只顾眼前
  
最优，并且当前的选择是不会依赖以前的选择的，而dp，在选择的时候是从以前求出的若干个与本步骤
  
相关的子问题中选最优的那个，加上这一步的值来构成这一步那个子问题的最优解
  


  
讲得再多不如看几个很经典的样例，带你初步入门dp
  
我不会讲很多具体该怎么做，而是剖析这些经典例题中的dp思想，真真正正的1懂得了dp思想的话，做题事
  
半功倍（自己深有体会）
  


  
样例1：数字三角形问题
  
7
  
3 8 
  
8 1 0 
  
2 7 4 4 
  
4 5 2 6 5 
  
从顶部向下走，每次只能走下面或者右下，走完全程，问你怎么走使得权值最大（问题描述不是很详细，关
  
于数字三角形问题是什么问题请百度）
  
那么dp的思想到底是怎么体现的呢?
  
dp是要先分解成很多相互联系的子问题，要解决一个子问题，依赖于前面和此子问题相关的已经解决的子
  
问题中选一个最优的加上这个子问题的解，就是这个子问题的最优解
  
具体做法：
  
1.分析问题的最优解，找出最优解的性质，并刻画其结构特征：
  
问题的最优解：所有走法中最大的权值是多少？
  
最优解的性质和结构特征：只能向正下或者右下走，每走一行的最大权值等于前面一行的最大权值加上这一
  
行的走的两个方向中的最大值
  
2.递归的定义最优值：
  
要找到从0行出发的最优值，就要找到从第1行出发的最优值
  
要找到从1行出发的最优值，就要找到从第2行出发的最优值
  
………………………
  
要找到第3行出发的最优值，就要找到从最后一行出发的最优值
  
为什么是这样呢？我们分析一下
  
题目要你求从0行出发的最优值，那么我们就是要找到从第一行出发的最优值，加上第0行到第1行的最优值
  
但是，很重要的一点，我们需要递归求解，要先求解从倒数第一行出发的最优值，然后根据从倒数第一行出
  
发的最优值求出从倒数第二行出发的最优值
  
3.采用自底向上的方式计算问题的最优值：
  
这个就是我上面说的，要先求解从倒数第一行出发的最优值，然后根据从倒数第一行出发的最优值求出从倒
  
数第二行出发的最优值，自底向上的计算，迭代的方式求解子问题
  
4.根据计算最优值时间得到的信息，构造最优解
  
这个就是问你具体是怎么走的，我们需要在求解子问题的时候保存一些信息，采用构造出最优解（最优值和
  
最优解是不同的，最优值在本问题中是一个走法中权值之和最大的那一个，而最优解是具体的走法），这里
  
题目没有要求就是不用去构造最优解，构造起来也挺麻烦的。。。。
  
解法：
  
dp【i】【j】：代表从第i行第j列出发得到的最优值
  
dp【i】【j】=max（dp【i+1】【j】，dp【i+1】【j+1】）+a【i】【j】
  
表示从第i行第j列出发的最优值等于到i+1行的两种走法中最大的那一个加上出发点的权值
  
贴个链接：
  https://www.cnblogs.com/yinbiao/p/8995253.html

  
贴个代码：
  

   
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);//n行
    int a[n][n];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    int dp[n][n];
    memset(dp,0,sizeof(dp));
    for(int j=0;j<n;j++)
    {
        dp[n-1][j]=a[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])+a[i][j];
        }
    }
    printf("%d\n",dp[0][0]);
    return 0;
}
  
  


  
经典样例2：最长公共子序列问题 （LCS问题）
  
给你两个序列，问你他们的最长LCS序列的长度是多少？（序列可以是不连续的，只要元素的相对位置一
  
样）（不了解LCS问题的自行百度）
  
那么在LCS问题中dp的思想体现在哪里呢？
  
重复子问题：(超级容易发现的一个）
  
我们要求x1~xi，Y1~Yj的LCS，那么是不是要求x1~xi-1，Y1~Yi-1的LCS
  
我们要求x1~xi-1，y1~yi-1的LCS，那么是不是要求x1~xi-2，Y1~yi-2的LCS
  
所以我们要求的x1~xi，Y1~Yj的LCS这个大问题中，包含了很多的重复子问题
  
具体做法：
  
c【i】【j】表示x1~xi，Y1~Yj的LCS序列长度
  
x【i】==y【j】 c【i】【j】=c【i-1】【j-1】+1
  
x【i】！=y【j】  c【i】【j】=max（c【i-1】【j】，c【i】【j-1）
  
i==0||j==0 c【i】【j】=0
  
贴个代码（求最优值和最优解）
  

   
#include<bits/stdc++.h>
#define max_v 1005
using namespace std;
char x[max_v],y[max_v];
int dp[max_v][max_v];
int l1,l2;
int dfs(int i,int j)
{
    if(i==-1||j==-1)
        return 0 ;
    if(x[i]==y[j])//来自左上角
    {
        dfs(i-1,j-1);
        cout<<x[i]<<" ";//先递归到最后再输出，，这样就是顺序的
    }
    else
    {
        if(dp[i-1][j]>dp[i][j-1])//来自上面
        {
            dfs(i-1,j);
        }
        else//来自左边
        {
            dfs(i,j-1);
        }
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        scanf("%s",x);
        scanf("%s",y);
        int l1=strlen(x);
        int l2=strlen(y);
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=l1; i++)
        {
            for(int j=1; j<=l2; j++)
            {
                if(x[i-1]==y[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",dp[l1][l2]);
        dfs(l1,l2);
        cout<<endl;
    }
    return 0;
}


/*
2
ABCBDAB
BDCABA
*/
  
  


  
经典样例三：矩阵连乘问题，纸牌问题，石头合并问题（都是一类问题，一起分析）
  
给定n个矩阵{A1，A2…..An}，其中A【i】与A【i+1】是可乘的，如何确定计算的次序，使得乘法的总次数最少
  
首先我们要明白，计算的次序不同，那么乘法的总次数也不同
  
类似的问题：给你n张牌，每张排都有一个数字，相邻的两张牌的权值可以相乘，相乘的两张牌可以合并为
  
一张牌，新牌的权值是原来的两张牌的乘积
  
这个问题还有石头合并问题都是同一类的问题，属于区间dp问题
  
石头合并问题：给你一堆石头，排成一行，相邻的两个石头可以合并，合并成的石头的权值为原来两个石头
  
的权值之和
  
先来分析矩阵连乘问题：
  
给你一个一维数组
  
30，35，15，5，10，20，25
  
只要相邻的矩阵才可以相乘
  
思考一下，dp的思想是如何体现的
  
第一步我们是要把问题分解成很多互相有联系的子问题（重复子问题是用dp的基础）
  
简单的思考一下，每次矩阵相乘，最简单的就是两个可以相乘的矩阵相乘（A1，A2，A3），那最大的乘法次数就是A1*A2*A3
  
但是如果是多个呢，我们是不是可以简化成下面这样
  
A【i】,A【i+1】………………….A【k】………………A【j-1】，A【j】
  
讲他们分成两个抽象矩阵
  
第一个：A【i】….A【k】
  
第二个：A【k+1】…..A【j】
  
把大问题抽象成两个抽象矩阵相乘，那么更加最简单的那种抽象一下就知道求所有矩阵乘法的最大次数，就
  
是求第一个抽象矩阵自己内部要乘的次数和第二个抽象矩阵内部自己要求的乘法次数然后加上这这两个抽象
  
矩阵合并为一个大的抽象矩阵要乘的次数
  
那么大问题是这样的，大问题里面是不是有很多这样的小问题，而且这些小问题还是重复的，比如A【k】
  
的选择不同，那么乘的次序结果也不一样，A【k】的选择可以导致很多问题都有重复的部分，如果多次计
  
算的话，无疑是很不明智的，这样的话跟分治就是没有什么区别了，这样的问题就叫做重复子问题
  
A【k】的选择不同的话，会导致子问题有很多重复的部分，前面我们说了的，同时A【k】的选择不同的话
  
会导致两个抽象矩阵相乘的结果也不一样，所以我们就要在所有的A【k】选择中找一个最小的
  
所以我们现在在这个问题里面找到了dp思想的具体体现：大量的重复子问题
  
具体做法：
  
dp【i】【j】：代表矩阵i，矩阵i+1………….矩阵j的最少乘法次数
  
总结上述：
  
dp【i】【j】=min（dp【i】【k】+dp【k+1】【j】
  
i<=k<=j-1
  
贴个代码：
  

   
#include<bits/stdc++.h>
using namespace std;
#define max_v 1005
int dp[max_v][max_v],a[max_v],s[max_v][max_v];
void f(int i,int j)
{
    if(i==j)
        return ;
    f(i,s[i][j]);
    f(s[i][j]+1,j);
    printf("A[%d:%d]*A[%d:%d]\n",i,s[i][j],s[i][j]+1,j);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(int i=1;i<=n;i++)
    {
        dp[i][i]=0;
    }

    for(int r=2;r<=n;r++)
    {
        for(int i=1;i<=n-r+1;i++)
        {
            int j=i+r-1;
            dp[i][j]=dp[i+1][j]+a[i-1]*a[i]*a[j];
            s[i][j]=i;
            for(int k=i+1;k<j;k++)
            {
                int t=dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
                if(t<dp[i][j])
                {
                    dp[i][j]=t;
                    s[i][j]=k;
                }
            }
        }
    }
    f(1,n);
}

/*
6
30 35 15 5 10 20 25

A[2:2]*A[3:3]
A[1:1]*A[2:3]
A[4:4]*A[5:5]
A[4:5]*A[6:6]
A[1:3]*A[4:6]
*/
  
  
分析了矩阵连乘问题，再来分析一下石头合并问题
  
石头合并问题：其实这个问题跟矩阵连乘问题真的是一样的
  
非常非常的类似
  
A1，A2………………….An
  
也是分解成两个抽象的石头
  
A【i】，A【i+1】………A【k】……….A【j】
  
第一个抽象石头：A【i】……..A【k】
  
第二个抽象石头：A【k+1】…….A【j】
  
我们现在把大问题分解成了两个抽象的石头合并问题
  
问的是你合并完成后最小的权值是多少
  
大问题的最小权值等于第一个抽象石头合并的权值加上第二个抽象石头合并的权值，再加上这两个抽象的石头合并的权值
  
我们知道，A【k】的选择不同，会导致最后权值的不同，也会导致大量重复的子问题（前面在矩阵连乘wen他中具体分析了）
  
所以我们要在所有的A【k】选择中，选择一个合并花费最小的
  
现在我们把大问题分解成了这样一个问题，那么每个抽象的石头也还可以当初一个大问题继续分解呀，所以
  
就分解成了很多子问题
  
具体做法：
  
dp【i】【j】：代表合并第i到第j个石头的最小花费
  
sum【i】：表示1~i个石头的权值之和
  
dp【i】【j】=min（dp【i】【k】+dp【k+1】【j】）+sum【j】-sum【i】+a【i】
  
为什么是sum【j】-sum【i】+a【i】呢？
  
因为我们要合并从第i个石头到第j个石头所需要的花费就是第i个石头到第j个石头的权值的和呀
  
贴个代码：
  

   
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int a[n+1];
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        int sum[n+1];
        int dp[n+1][n+1];
        for(int i=1; i<=n; i++)
        {
            int t=0;
            for(int j=1; j<=i; j++)
            {
                t=t+a[j];
            }
            sum[i]=t;
        }
        for(int i=1; i<=n; i++)
        {
            dp[i][i]=0;
        }
        for(int r=2; r<=n; r++)
        {
            for(int i=1; i<=n-r+1; i++)
            {
                int j=i+r-1;
                int t=dp[i][i]+dp[i+1][j]+sum[j]-sum[i]+a[i];
                for(int k=i; k<=j-1; k++)
                {
                    if(t>dp[i][k]+dp[k+1][j]+sum[j]-sum[i]+a[i])
                    {
                        t=dp[i][k]+dp[k+1][j]+sum[j]-sum[i]+a[i];
                    }
                }
                dp[i][j]=t;
            }
        }
        printf("%d\n",dp[1][n]);
    }
    return 0;
}

/*
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239
*/
  
  


  
经典样例四：最长递增子序列
  
比如
  
1，7，3，5，8，4，8
  
问你最长的递增的子序列的长度是多少
  
这个问题的最优解有多个，但是最优值只有一个：长度为4
  
1，3，5，9
  
1，3，5，8
  
1，3，4，8
  
这三个都是最优解，但是他们长度都是一样的，长度为4
  
这些是我们看出来的
  
那我们如何用dp的思想解题呢
  
第一步分解成很多互相有联系的子问题
  
要求第n个元素结尾的LIS序列的长度，就要求以第n-1个元素结尾的LIS序列的长度
  
要求第n-1个元素结尾的LIS序列的长度，就要求以第n-2个元素结尾的LIS序列的长度
  
…………..
  
假设第n-1个元素结尾的LIS序列的长度为2，且第n个元素是大于第n-1个元素的（递增的），那么以第n
  
个元素结尾的LIS序列的长度不就是以第n-1个元素结尾的LIS序列的长度加上1吗？
  
再回过头来看看这些子问题
  
他们中是不是含有大量重复的子问题
  
dp【n】：代表以第n个元素结尾的LIS序列的长度
  
比如我要求dp【n】，就要求dp【n-2】，dp【n-3】
  
在要求dp【n-1】的时候，也还要求dp【n-2】，dp【n-3】一次
  
这个就是求了很多次，想想当n足够大的时候，子问题足够多的时候，求的重复的子问题是不是很多很多
  
这样的话速度太慢
  
所以这个时候，dp的作用就是体现出来了，保存已经求解过的子问题的值，下次又遇到这个子问题的时
  
候，直接拿出来用就好啦
  
做法：
  
dp【1】=1
  
dp【i】=max（dp【j】+1） 要求：a【j】<a【i】，j<i
  
就是在第i个元素的前面找到LIS序列长度最大的，加上1，（先决条件是递增的）
  
贴个代码：（最优值和一个最优解）
  

   
#include<bits/stdc++.h>
using namespace std;
#define max_v 1005
int a[max_v],dp[max_v];
void f(int n,int result)
{
    bool flag=false;
    if(n<0||result==0)
        return ;
    if(dp[n]==result)
    {
        flag=true;
        result--;
    }
    f(n-1,result);
    if(flag)
        printf("%d ",a[n]);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            int t=0;
            for(int j=0;j<i;j++)
            {
                if(a[j]<a[i])
                {
                   if(t<dp[j])
                   {
                       t=dp[j];
                   }
                }
            }
            dp[i]=t+1;
        }
        int t=0;
        for(int i=0;i<n;i++)
        {
            if(t<dp[i])
            {
                t=dp[i];
            }
        }
        printf("%d\n",t);
        f(n,t);
        printf("\n");
    }
    return 0;
}
/*
输入：
7
1 7 3 5 9 4 8
输出：
4
1 3 4 8*/
  
  


  
经典样例五：最大子段和问题
  
比如：
  
-2，11，-4，13，-5，-2
  
什么叫最大字段和？就是连续的数字的和最大是多少，注意是段，而不是序列，序列可以是离散的，而段必
  
须的连续的
  
所以这个问题dp思想体现在哪里呢？
  
这个问题其实跟LIS，LCS问题都差不多，都是线性dp问题
  
第一步：分解成很多有联系的子问题
  
要求以第n个元素结尾的最大字段和是多少，就要求以第n-1个元素结尾的最大字段和是多少
  
要求以第n-1个元素结尾的最大子段和是多少，就要求以第n-2个元素结尾的最大字段和是多少
  
为什么是这样呢？
  
仔细思考一下
  
以求第n-1个元素的1最大字段和为例
  
如果我们知道了以第n-2个元素的最大字段和是多少，如果是正的，加上第n个元素值即可，如果是负数，
  
那还不如不加呢，这样第n个元素的最大字段和还大一点，因为你加上一个负数肯定比原来的数小了呀
  
那么dp思想中的重复子问题体现在哪里呢？
  
体现在第一步，跟LIS问题中的体现是一样的，这里不再赘述
  
贴个代码：（最优解）
  

   
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n+1];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int dp[n+1];
        dp[1]=a[1];
        for(int i=2;i<=n;i++)
        {
            int x=dp[i-1];
            if(x<0)
            {
                x=0;
            }
            dp[i]=x+a[i];
        }
        int maxvalue=dp[1];
        for(int i=2;i<=n;i++)
        {
            if(maxvalue<dp[i])
            {
                maxvalue=dp[i];
            }
        }
        printf("%d\n",maxvalue);
    }
    return 0;
}
/*
输入：
2
6
-2 11 -4 13 -5 -2
输出；
20
*/
  
  


  
经典样例六：01背包问题
  
背包问题可以说是很经典的问题之一了，01背包问题，就是说每个物品只有两种选择，装还不装，且物品
  
不可分割
  
我先不讲01背包问题应该怎么做，讲01背包里面蕴含的dp思想
  
dp适用于多阶段决策问题，就是每个阶段都要做决策，且你做的决策会影响的最终的结果，导致最终结果的值有所不同
  
这个决策的概念在01背包里面用的可以说是体现的非常非常的透彻了，因为你每个阶段都要做决策呀，这
  
个物品我到底是选还是不选呢
  
声明一个 大小为  m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，
  
（1）. j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
  
m[ i ][ j ] = m[ i-1 ][ j ]
  
（2）. j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
  
如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。
  
如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）
  
究竟是拿还是不拿，自然是比较这两种情况那种价值最大。
  
状态转移方程：
  
if(j>=w[i])
     m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
 else
     m[i][j]=m[i-1][j];
  
代码如下：（二维dp解决01背包问题，一维dp解决01背包问题）
  

   
#include<bits/stdc++.h>
using namespace std;
int ZeroOnePack(int v[],int w[],int n,int c)//v1,v2....vn价值  w1,w2,w3...wn重量 n表示n个物品 c表示背包容量
{
    int dp[n+1][c+1];
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=c; j++)
        {
            if(j>=w[i])
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//第i个物品放入之后，那么前面i-1个物品可能会因为剩余空间不够无法放入
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }

        }
    }
    return dp[n][c];
}
//空间优化，采用一维数组
int ZeroOnePack_improve(int v[],int w[],int n,int c)//v1,v2....vn价值  w1,w2,w3...wn重量 n表示n个物品 c表示背包容量
{
    int dp[c+1];
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        for(int j=c; j>=0; j--)
        {
            if(j>=w[i])
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

        }
    }
    return dp[c];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        int n,c;
        scanf("%d %d",&n,&c);
        int v[n+1],w[n+1];
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&v[i]);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&w[i]);
        }
        // printf("%d\n",ZeroOnePack(v,w,n,c));
        printf("%d\n",ZeroOnePack_improve(v,w,n,c));

    }
    return 0;
}

/*
1
5 10
1 2 3 4 5
5 4 3 2 1

14
*/
  
 
 
 
 
 
 
 
  
 
  
 
  
 
  
 
  
 
  
 
 
 

一、Python简介
 
Python（英国发音：/ˈpaɪθən/美国发音：/ˈpaɪθɑːn/）,是荷兰科学家吉多·范罗苏姆（Guido van Rossum），在1989年期间开发的计算机编程语言。在Python语言中，一切皆为对象，即使函数也是对象，有自身的属性。Python是解释型编程语言，运行Python程序时，需要将解释器翻译Python代码。
 
Python是一种不受局限、跨平台的开源编程语言，其数据处理速度快、功能强大且简单易学，在数据分析与处理中被广泛应用。而且，Python采用解释运行的方式，编写后无需进行编译即可直接通过解释器执行，具有典型的动态语言特点，编程效率极高。Python是完全面向对象的语言，数字、模块、字符串、数据结构都是对象，并且支持常见的类概念，如继承，重载，派生，多重继承。
 
2017年7月20日，IEEE发布2017年编程语言排行榜：Python高居首位。2018年3月，该语言作者在邮件列表上宣布Python 2.7将于2020年1月1日终止支持。用户如果想要在这个日期之后继续得到与Python 2.7有关的支持，则需要付费给商业供应商。
 
 
二、语言特点
 
1、简单清晰
 
Python是一种代表简单主义思想的语言，之所以这么说，是因为Python是一门清晰的语言，它的作者在设计它的时候，总的指导思想是，对于一个特定的问题，只要一种最好的方法来解决就好了。Python和其他大多数语言的一个主要区别就是完全由每行的首字符缩进来界定一个模块的界限，不可否认，通过使用缩进使得Python程序显得清晰和美观。阅读一个优秀的Python程序就感觉像是在读英语一样，Python的这种伪代码特性使开发者能够专注于解决问题而不是去搞明白语言本身。
 
2、纯面向对象
 
与传统的面向对象语言fC++，Java)不同的是，在Python的世界里，万物皆为对象。模块，类，函数，变量，类的实例都属于Python中的对象，例如函数是一个对象，它有自己的代码块，注释文档以及变量字典。
 
3、支持面向过程和面向对象编程
 
Python不强制你使用类的概念组织软件，你可以以面向过程的思想编写你的软件。这个类似于“+，完全可以不用c++面向对象的特性编写软件，退化为c语言了。
 
4、非常丰富的标准库支持
 
Python提供了一套功能完善的内置库支持，除了基本的数据结构，如链表，字典，字符串操作等，还提供了很多在程序中会经常使用的操作，比如正则表达式，配置文件，tar文件格式的创建和读取。
 
5、具有良好的可扩展性
 
Python与c／c++语言有良好的交互性，你既可以在Python中调用用C实现的模块，也可以在C中调用Python解析器。这个类似于Java的JNI了。对于一些性能要求高的模块，用C语言编写Python模块是一种不错的选择。
 
ok，这就是Python~

        汉诺塔问题是法国数学家编写的一个古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。   
        这个问题是一个典型的递归问题，通过多重递归，最后简化为对一个盘子的操作，我们不需要关心程序具体的细节，只需要关注大体的步骤，就像“把大象装进冰箱需要分几步”这个问题，只需要三步：打开冰箱、把大象放进去、关上冰箱。汉诺塔问题也是如此，每一块金片移动到目的地，只需要三步。下面我们就来讨论，具体该怎么去思考这个问题。
                        
我们将三根柱子用左柱，中柱，右柱表示  

如果只有一块金片的话，我们要怎么处理呢，是不是可以这样想：将金片从左柱移动到右柱就可以了
那么继续考虑这种情况：有两块金片的时候，要怎么处理呢，我们把第一块金片放到中柱上，再把左柱底下的金片移动到右柱上，再将中柱的金片移动到右柱上，就达成了目标
思考完两片柱子的移动之后，其实我们已经有一些思路了，假如有n块（n>=2）金片，我们以四块为例，那么我们的大步骤是这样的：


1.将最底下的一片看作一片，将上面的3片（n-1）片看作一片
2.将n-1片金片通过右柱的帮助，最终移动到中柱子上，不需要具体关心如果实现，我们只要这么想即可
3.将最底下的一片通过中柱的帮助放到右柱上（尽管不需要中柱的帮助，我们还是这么说）
4.那么就会变成这样的情况：


最右边的金片是已经不需要移动的，也不会对我们造成影响，我们在心理就当没有这块金片，那么现在问题就变成了：将三块金片从中柱移动到右柱上，这个场景是不是很相似呢，我们不需要考虑三个柱子的位置，只需要看到：起始位置，中间位置，目标位置。那么跟刚才的问题就是一样的，刚才是需要把四块金片从起始位置，通过中间位置的帮助，到达目标位置，现在化繁为简，变成三块了，那么我们如果继续重复这样的思路：把最底下的看作一块，剩余的两块看作一块，再重复三个步骤：
1.把底下的看作一块，把上面的其余金片看作一块
2.将上面的一大块金片通过右柱的帮助，最终移动到左柱子上，不需要具体关心如果实现，我们只要这么想即可
3.将最底下的一片通过左柱的帮助放到右柱上（尽管不需要中柱的帮助，我们还是这么说）

4.那么又变成了这样的情况：


这样就变成了两个金片的移动问题了，可想而知再次重复上面的步骤，我们就可以化做一个金片的移动问题，那么一片金片的移动就只是搬过去就好了。
通过上面的分析我们可以看出来：任何数量的金片移动，都可以一步步解析为一块金片的移动，而我们能够清晰地描述出一块金片的移动过程，那么问题就可以抽象地描述出来了
下面是用Java的实现：
public class HanoiDemo {

	public static void main(String[] args) {
		hanoi(20,"左柱","中柱","右柱");
	}
	
	
	//方法理解：将n块金片，从a盘子上，通过b盘子的帮助，移动到c盘上
	static int counter =0;
	public static void hanoi(int n,String a,String b,String c) {
		if(n==1) {
			System.out.println("将盘子从"+a+"移动到"+b+"上,第"+counter+"次移动");
			counter++;
		}
		if(n>=2) {
			hanoi(n-1,a,c,b);
			hanoi(1,a,b,c);
			hanoi(n-1,b,a,c);
		}
	}

}
方法就只有短短的十行，重要的还是对于思想的理解，如果对原理了解透了，计算机可以帮我们做更多的事