C++动态规划超详细总结-创新互联

动态规划

首先来介绍一下动态规划,但我不想用过于官方的语言来介绍。动态规划是一种思想,它常用于最优解问题(即所有问题包括所有子问题的解为最优解),它有点像递推,是在已知问题的基础上解决其他问题。这种思想较为复杂,也是很多 OIer 的痛。

成都创新互联于2013年开始,先为平桂等服务建站,平桂等地企业,进行企业商务咨询服务。为平桂企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。解题步骤
  1. 把一个问题拆分成很多小问题

  1. 找出最初的状态(即上文“在已知问题的基础上”的已知部分)

  1. 建立状态转移方程(即上文“解决其他问题”)

其实状态转移方程有点像找规律,通过前面的规律推出后面。

例题讲解

我们先从最简单经典的跳台阶问题开始。

台阶问题 题目描述

有 N 级的台阶,你一开始在底部,每次可以向上迈最多K级台阶(1或2级),问到达第N级台阶有多少种不同方式。

输入格式

两个正整数N,K。

输出格式

一个正整数,为不同方式数。

样例 #1 样例输入 #1
5 2
样例输出 #1
8
台阶问题的解法 思路

首先题目的意思就是 N 阶台阶,每次可以迈 1或2 阶,问有几种迈的方法。

这里我们不妨设一个函数为结果。

每阶台阶可以向上走 1或2阶,那么第 N 阶台阶一定是从 N-1 或者 N-2 阶台阶来的,第 N-1 或 N-2 阶台阶也一定是从 N-3/N-2 或 N-3/N-4 来的,以此类推。

那么,状态转移方程为

dp[N]=dp[N-1]+dp[N-2]

怎么样,是不是很简单?

难度提升!

代码
#includeusing namespace std;
int m,dp[3],n;
int main(){
  cin >>n;
  for(int i=1;i<=n;i++){
    cin >>m;
    dp[0]=1;
    dp[1]=1;
    if(m<2) break;
    for(int j=2;j
田忌赛马 题目描述

我国历史上有个著名的故事: 那是在2300年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马:常规马,上级马,超级马。一共赛三局,每局的胜者可以从负者这里取得200银币。每匹马只能用一次。齐王的马好,同等级的马,齐王的总是比田忌的要好一点。于是每次和齐王赛马,田忌总会输600银币。

田忌很沮丧,直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后,三场比赛下来,轻松而优雅地赢了齐王200银币。这实在是个很简单的计策。由于齐王总是先出最好的马,再出次好的,所以田忌用常规马对齐王的超级马,用自己的超级马对齐王的上级马,用自己的上级马对齐王的常规马,以两胜一负的战绩赢得200银币。实在很简单。

如果不止三匹马怎么办?这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边,把齐王的马放右边。田忌的马A和齐王的B之间,如果田忌的马胜,则连一条权为200的边;如果平局,则连一条权为0的边;如果输,则连一条权为-200的边……如果你不会求最佳匹配,用最小费用大流也可以啊。 然而,赛马问题是一种特殊的二分图最佳匹配的问题,上面的算法过于先进了,简直是杀鸡用牛刀。现在,就请你设计一个简单的算法解决这个问题。

输入格式

第一行一个整数n,表示他们各有几匹马(两人拥有的马的数目相同)。第二行n个整数,每个整数都代表田忌的某匹马的速度值(0<= 速度值<= 100)。第三行n个整数,描述齐王的马的速度值。两马相遇,根据速度值的大小就可以知道哪匹马会胜出。如果速度值相同,则和局,谁也不拿钱。

数据规模

对于20%的数据,1<=N<=65;

对于40%的数据,1<=N<=250;

对于100%的数据,1<=N<=2000。

输出格式

仅一行,一个整数,表示田忌大能得到多少银币。

样例 #1 样例输入 #1
3
92 83 71
95 87 74
样例输出 #1
200
田忌赛马问题的解法

这道题除了 DP ,还有简单的做法,我直接放代码,但为了学习 DP,我还是讲一下 DP 做法。

简单解法
//田忌赛马
#include#include
using namespace std;
int n,qsp[2010],tsp[2010];
int main(){
    cin>>n;
    for(int i=0;i>tsp[i];
    }
    for(int i=0;i>qsp[i];
    }
    sort(qsp,qsp+n);
    sort(tsp,tsp+n);
    int tmin=0,tmax=n-1,qmin=0,qmax=n-1,jb=0;
    for(int i=0;iqsp[qmin]){
            jb+=200;
            tmin++;
            qmin++;
        }
        else if(tsp[tmax]>qsp[qmax]){
            jb+=200;
            tmax--;
            qmax--;
        }
        else if(tsp[tmin]

这段代码大家应该能看懂,我不做讲解。

DP 做法

看到这道题,大家可能毫无头绪(做题时不要损坏设备)

首先,田忌拥有比赛的“主动权”,因为他可以根据齐王出的马来出马。可以假设齐王出马的顺序是从强到弱,那么田忌出马应该是最强或最弱。用 f[i,j] 表示齐王出了 i 匹较强的马和田忌出了 j 匹较强的马。i-j 表示较弱的马比赛之后田忌获得的利益。

那么状态转移方程是

f[i][j]=max(f[i-1][j]+g[n-i+j+1][i],f[i-1][j-1]+g[j][i])

其中g[i][j] 表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后,田忌的第 i 匹马和齐王的第 j 匹马赛跑所能取得的盈利,胜为 200 ,负为 −200 ,平为 0。

代码
#include#include#include 
using namespace std;

const int N=2001,INF=-2e+8;
int a[N],b[N],g[N][N],f[N];

bool Cmp(int n1,int n2) {return n1>n2;}

int main()
{
    int n,Ans,i,j; scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]);
    sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (a[i]>b[j]) g[i][j]=200;
            else if (a[i]==b[j]) g[i][j]=0;
                 else g[i][j]=-200;
        }
    for (i=1;i<=n;++i) f[i]=INF;
    for (i=1;i<=n;++i)
    {
        f[i]=f[i-1]+g[i][i];
        for (j=i-1;j>0;--j)
            f[j]=max(f[j]+g[n-i+j+1][i],f[j-1]+g[j][i]);
        f[0]=f[0]+g[n-i+1][i];
    }
    Ans=f[1];
    for (i=2;i<=n;++i) Ans=max(Ans,f[i]);
    printf("%d\n",Ans);
    return 0;
}

怎么样,还能理解吗?

[ 真题 ] 纪念品

动态规划的难度和精髓在于状态转移方程。 ——鲁迅(我没说过这句话)

接下来这道题会让大家知道什么是真正的状态转移方程。

题目描述

小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;

2. 卖出持有的任意一个纪念品,以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。

T 天之后,小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。

小伟现在有 M 枚金币,他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T, N, M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量 N,小伟现在拥有的金币数量 M。

接下来 T 行,每行包含 N 个正整数,相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 P_{i,1},P_{i,2},……,P_{i,N},其中 P_{i,j} 表示第 i 天第 j 种纪念品的价格。

输出格式

输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

样例 #1 样例输入 #1
6 1 100
50
20
25
20
25
50
样例输出 #1
305
样例 #2 样例输入 #2
3 3 100
10 20 15
15 17 13
15 25 16
样例输出 #2
217
提示

【输入输出样例 1 说明】

最佳策略是:

第二天花光所有 100 枚金币买入 5 个纪念品 1;

第三天卖出 5 个纪念品 1,获得金币 125 枚;

第四天买入 6 个纪念品 1,剩余 5 枚金币;

第六天必须卖出所有纪念品换回 300 枚金币,第四天剩余 5 枚金币,共 305 枚金币。

超能力消失后,小伟最多拥有 305 枚金币。

【输入输出样例 2 说明】

最佳策略是:

第一天花光所有金币买入 10 个纪念品 1;

第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3,剩余 1 枚金币;

第三天必须卖出所有纪念品换回216 枚金币,第二天剩余1枚金币,共 217 枚金币。

超能力消失后,小伟最多拥有 217 枚金币。

纪念品问题的解法 思路

这道题其实是动态规划和完全背包问题的结合。

我们进行 t−1 轮完全背包:

把今天手里的钱当做背包的容量,

把商品今天的价格当成它的消耗,

把商品明天的价格当做它的价值,

每一天结束后把总钱数加上今天赚的钱,直接写背包模板即可。

另: 在这道题中,我们可以把商品和钱看成同样的东西,因为题目中说了:可以当天买当天卖,所以不必考虑跨天的买卖,只需考虑当天的即可,这满足动态规划对于最优化原理和无后效性的要求,可以大胆地购买。

除第一天只有购入过程、最后一天只有售出过程外,每天都有售出与购入两个过程。两个过程互不干扰。

为获得更多的“资金”,不妨令每日的售出过程先于购入过程。

每天的购入过程与次日的售出过程(差价)构成一次完全背包。或者说,完全背包是在“第 X.5 天”进行的。

定义:

f[i]为用 i 元钱去购买商品所能盈利的大值(不含成本)

状态转移方程: f[j]=max(f[j],f[j−price[i][k]]+price[i][k+1]−price[i][k]);

代码
#include#includeusing namespace std;
const int N = 101;
const int M = 10001;
int n, m, t, price[N][N], f[M];
int main()
{
    cin >>t >>n >>m;
    for(int i = 1; i<= t; i++)
        for(int j = 1; j<= n; j++)
            cin >>price[j][i];
          //读入每种商品每天的价格
    for(int k = 1; k< t; k++)
    {
        memset(f, 0, sizeof f);//每轮开始前都要制零
        for(int i = 1; i<= n; i++)
            for(int j = price[i][k]; j<= m; j++)//完全背包,正着循环
                f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
      
        m += f[m];//加上盈利的钱,进入下一轮买卖
    }
    cout<< m;
    return 0;
}

这样就好了(

最后

这篇博客到这里也就结束了,今天主要是介绍了《简单》的动态规划问题(bushi,题目提交地址可以看我的 OJ。(

拜拜~~

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站名称:C++动态规划超详细总结-创新互联
链接地址:http://pwwzsj.com/article/higeo.html