动态规划-阿里云开发者社区

开发者社区> ggbond233> 正文

动态规划

简介: 具体来说,动态规划的一般流程就是三步:暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。
+关注继续查看

动态规划

具体来说,动态规划的一般流程就是三步:暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法

就思考流程来说,就分为一下几步:找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系

动态规划三要素

  1. 重叠子问题
  2. 最优子结构
  3. 状态转移方程

框架

  1. 明确 base case
  2. 明确「状态」:dp函数的参数,dp数组的索引
  3. 明确「选择」:求最值时的选择
  4. 定义 dp 数组/函数的含义

按上面的套路走,最后的结果就可以套这个框架:

# 初始化 base case

dp[0][0][...] = base

# 进行状态转移

for 状态1 in 状态1的所有取值:

   for 状态2 in 状态2的所有取值:

       for ...

           dp[状态1][状态2][...] = 求最值(选择1,选择2...)

确定base case就是dp[i]最基础的情况,初始化为至少的可能即可

状态是原问题和子问题中变化的数据,dp数组的参数一般为状态(dp数组的索引一般为状态)

选择是导致状态改变的原因,for循环遍历所有选择,比较出最值即可选出最优解

总结一下如何找到动态规划的状态转移关系:

1、明确 dp 数组所存数据的含义。这一步对于任何动态规划问题都很重要,如果不得当或者不够清晰,会阻碍之后的步骤。

2、根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0...i-1] 都已知,想办法求出 dp[i],一旦这一步完成,整个题目基本就解决了。

但如果无法完成这一步,很可能就是 dp 数组的定义不够恰当,需要重新定义 dp 数组的含义;或者可能是 dp 数组存储的信息还不够,不足以推出下一步的答案,需要把 dp 数组扩大成二维数组甚至三维数组。

0-1背包问题

给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?

这个题目中的物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。这也许就是 0-1 背包这个名词的来历。

1. 明确 状态 和 选择

如何才能描述出一个背包问题?

  1. 给出背包容量限制
  2. 给出几个可选物品

状态是子问题相比原问题变化的数据,所有状态有两个,即【背包的容量】和【可选择的物品】

选择是对于每件物品,【装进背包】或【不装进背包】

明白了状态和选择,动态规划问题基本上就解决了,只要往这个框架套就完事儿了:

for 状态1 in 状态1的所有取值:

   for 状态2 in 状态2的所有取值:

       for ...

           dp[状态1][状态2][...] = 择优(选择1,选择2...)

2. 根据 状态 定义dp数组

几个状态就是几维数组

dp数组是描述问题局面的一个数组。即用dp数组把状态表示出来

首先看看刚才找到的「状态」,有两个,也就是说我们需要一个二维dp数组,一维表示可选择的物品,一维表示背包的容量。

dp[i][w]的定义如下:对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是dp[i][w]

比如说,如果 dp[3][5] = 6,其含义为:对于给定的一系列物品中,若只对前 3 个物品进行选择,当背包容量为 5 时,最多可以装下的价值为 6。

PS:为什么要这么定义?便于状态转移,或者说这就是套路,记下来就行了。

根据这个定义,我们想求的最终答案就是dp[N][W]。base case 就是dp[0][..] = dp[..][0] = 0,因为没有物品或者背包没有空间的时候,能装的最大价值就是 0。

细化上面的框架:

int dp[N+1][W+1]

dp[0][..] = 0

dp[..][0] = 0

for i in [1..N]:

   for w in [1..W]:

       dp[i][w] = max(

           把物品 i 装进背包,

           不把物品 i 装进背包

       )

return dp[N][W]

3. 根据 选择 求出状态转移方程

简单说就是,上面伪码中「把物品i装进背包」和「不把物品i装进背包」怎么用代码体现出来呢?

这一步要结合对dp数组的定义和我们的算法逻辑来分析:

先重申一下刚才我们的dp数组的定义:

dp[i][w]表示:对于前i个物品,当前背包的容量为w时,这种情况下可以装下的最大价值是dp[i][w]

  1. 如果你没有把这第i个物品装入背包,那么很显然,最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛,那就继承之前的结果。
  2. 如果你把这第i个物品装入了背包,那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]
    首先,由于i是从 1 开始的,但wt数组和val数组下标从0开始,所以对valwt的取值是i-1
    dp[i-1][w-wt[i-1]]也很好理解:你如果想装第i个物品,你怎么计算这时候的最大价值?换句话说,在装第i个物品的前提下,背包能装的最大价值是多少?
    显然,你应该寻求剩余重量w-wt[i-1]限制下能装的最大价值,加上第i个物品的价值val[i-1],这就是装第i个物品的前提下,背包可以装的最大价值。

综上就是两种选择,我们都已经分析完毕,也就是写出来了状态转移方程,可以进一步细化代码:

for i in [1..N]:

   for w in [1..W]:

       dp[i][w] = max(

           dp[i-1][w],#第i件物品不放进背包

           dp[i-1][w - wt[i-1]] + val[i-1]#第i件物品放进背包

       )

return dp[N][W]

4. 编写完整代码+处理边界

每一层循环是一种状态

三种状态那么就三层循环

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {

   // vector 全填入 0,base case 已初始化

   vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));

   for (int i = 1; i <= N; i++) {

       for (int w = 1; w <= W; w++) {

           if (w - wt[i-1] < 0) {

               // 当前背包容量装不下,只能选择不装入背包

               dp[i][w] = dp[i - 1][w];

           } else {

               // 装入或者不装入背包,择优

               dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],

                              dp[i - 1][w]);

           }

       }

   }

   return dp[N][W];

}

例题1

背包体积和质量有限,求在体积和质量的范围内所能装载的物品价值最大是多少?

输入格式:

第一行 两个数 体积最大值(<400)和质量最大值(<400)

第二行 一个数 食品总数N(<50)

第三行-第3+N行

每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)

输出格式:

一个数 所能达到的最大卡路里(int范围内)

输入样例:

320 350

4

160 40 120

80 110 240

220 70 310

40 400 220

输出样例:

在这里给出相应的输出。例如:

550

状态和选择

描述问题

  1. 背包体积
  2. 背包质量
  3. 可选的物品

状态即上述两个

选择是物品装或不装

根据 状态 定义dp数组

用dp数组来描述状态

dp[i][v][m]:对于前i个物品,当前背包体积为v,质量为m,这种情况下可以装的最大价值是dp[i][v][m]

base case 是dp[0][..][..]=dp[..][0][..]=dp[..][..][0],即没有物品,背包体积或质量为0,能装的最大价值为0

根据 选择 定义状态转移方程

体积数组是varr,质量数组是marr,价值数组是value

选择1:第i个物品未装入背包,直接继承上个结果

dp[i][v][m]=dp[i-1][v][m]

选择2:第i个物品装入背包

dp[i][v][m]=dp[i-1][v-varr[i-1]][m-marr[i-1]]+value[i-1]

编写代码(注意边界判断)

#include <bits/stdc++.h>

using namespace std;

//V背包体积,W背包重量,n是物品数

int V,W,n;

int v[100],w[100],value[100];//分别是物品的体积数组,重量数组,价值数组

int dp[51][401][401];//n,V,W

int main(){

   cin >> V >> W >> n;

   for(int i=1;i<=n;i++)

       cin >> v[i]>>w[i]>>value[i];

   for(int i=1;i<=n;i++)//遍历物品

       for(int j=1;j<=V;j++)//背包体积

           for(int k=1;k<=W;k++){//背包重量

               if(j-v[i]<0 || k-w[i]<0)

                   // 当前背包容量装不下,只能选择不装入背包

                   dp[i][j][k]=dp[i-1][j][k];

               else {

                   // 装入或者不装入背包,择优

                   dp[i][j][k]=max(

                   dp[i-1][j][k],//i物品没装进背包

                   dp[i-1][j-v[i]][k-w[i]]+value[i]

                   );

               }

           }

   cout << dp[n][V][W];

   return 0;

}

例题2

0-1背包问题是经典的动态规划问题,这个问题大多用这样的故事开场:一个小偷溜进了一家博物馆,博物馆里排列着N件珍稀古董,每件古董都有重量和价值,而小偷带来的背包有重量限制W。因此,小偷的目的就是要选择部分古董,使其总重量不超过W且总价值最大。这故事听上去就像小偷在逛超市一样能轻松自如地挑选,而真实的情况是小偷提心吊胆,尤其是每拿下一件古董,随时都有触动警报的危险,所以小偷想尽可能少带几件古董立马跑路,但他的职业“素养”又不允许他不把背包装满。你能帮他解决这个困境吗?

输入格式:

第一行中给出2个整数值N和W, 其中1<N≤100表示古董的数量,1<W≤2000表示背包的重量限制。 接下来N行数据,每行两个正整数。第i行(1≤i≤N)的整数vi和wi分别表示第i件古董的价值和重量。 vi和wi的值均不超过2000。

输出格式:

在一行中输出两个整数值,用空格分开。第一个整数表示装背包能获得的最大总价值,第二个整数表示在获得最大价值的条件下装入背包里的古董的最少数量。

输入样例:

6 6

1 1

2 2

3 3

4 4

5 5

6 6

输出样例:

在这里给出相应的输出。例如:

6 1

状态和选择

状态

  • 物品个数
  • 背包的重量

选择

  • 物品是否装到背包

根据 状态 定义dp数组

dp[i][w]:对于前i个物品,背包重量为w,所能装的最大价值为dp[i][w]

根据 选择 定义状态转移方程

  1. 装到背包:dp[i][w]=dp[i-1][w-warr[i]]+value[i]
  2. 未装到背包:dp[i][w]=dp[i-1][w]

编写代码

错误

#include<bits/stdc++.h>

using namespace std;

int N,W;//物品个数,背包重量

int varr[105],warr[105];//物品价值和重量数组

int dp[105][2005];//物品数目和背包重量的dp数组


int main(){

    cin>>N>>W;

    for(int i=1;i<=N;i++)

        cin>>varr[i]>>warr[i];

    for(int i=1;i<=N;i++)

        for(int j=1;j<=W;j++){

            if(j>=warr[i]){//背包剩余重量大于等于当前物品重量

                dp[i][j]=max(dp[i-1][j],dp[i-1][j-warr[i]]+varr[i]);

            }

            else

                dp[i][j]=dp[i-1][j];

        }

    cout<<dp[N][W];

    return 0;

}

正确

#include<bits/stdc++.h>


int N, W, vi[2005], wi[2005], dpv[2005], dpn[2005];

//dpv是用来存放最大价值的滚动数组

//dpn是用来存放最小数目的滚动数组

int min(int a, int b) {

    return a>b?b:a;

}

int main(void)

{

    scanf("%d%d", &N, &W);

    memset(dpv, 0, sizeof(dpv));

    memset(dpn, 1, sizeof(dpn));//函数将每一个二进制位都置为1,效果等同于将数组中每个值置为无穷大(int所能表示的最大正数)

    dpn[0] = 0;//填满容量为0的背包需要的物品数目为0

    for(int i = 1; i <= N; ++i)

        scanf("%d%d", &vi[i], &wi[i]);

    for(int i = 1; i <= N; ++i) {

        for(int j = W; j >= 1; --j) {

            if(j >= wi[i]) { //能放下当前物品

                if(dpv[j-wi[i]]+vi[i] >= dpv[j]) { //决定是否拿取当前物品

                    dpv[j] = dpv[j-wi[i]] + vi[i];//状态更新

                    dpn[j] = min(dpn[j], dpn[j-wi[i]]+1);//状态更新

                }

            }

        }

    }

    printf("%d %d\n", dpv[W], dpn[W]);

    return 0;

}

最长递增子序列

c++

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

public:

    int lengthOfLIS(vector<int>& nums) {

        //dp[i]以nums[i]结尾的最长递增子序列长度

        vector<int> dp(nums.size(),1);

        for (int i = 0; i < nums.size(); i++)

            

            for (int j = 0; j < i; j++)

                if (nums[i] > nums[j])

                    dp[i] = max(dp[i], dp[j] + 1);

        int res = 0;

        for (int i = 0; i < nums.size(); i++)

            res = max(res,dp[i]);

        return res;

    }

};

c

#include<stdio.h>

#include<malloc.h>

int lengthOfLIS(int* nums, int numsSize) {

 //创建dp[],dp[i]代表以nums[i]结尾的最长递增子序列的长度

 int* dp = (int*)malloc(sizeof(int) * numsSize);

 //确定base case,dp[i]至少为1

 for (int i = 0; i < numsSize; i++)

  dp[i] = 1;

 //如何求dp[i]呢?由数学归纳法,假设前i-1个dp数组元素已知,求dp[i]

 for (int i = 0; i < numsSize; i++) {

  for (int j = 0; j < i; j++)

   if (nums[i] > nums[j])

    dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i];

 }

 //根据dp的定义,遍历一遍dp数组,即可得出答案

 int res = 0;

 for (int i = 0; i < numsSize; i++)

  res = res > dp[i] ? res : dp[i];

 return res;

}

二维数组的array[][]行数和列数

  1. 二维数组的本质还是一维数组,可以理解为一维数组中存放的元素还是一维数组,且这些一维数组的长度不一定相等
  2. 二维数组的长度(行数,一行为一个一维数组)为一维数组的个数,即行数array.length
  3. 二维数组的宽度(列数)为第i行一维数组的长度,即array[i].length

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

递归(自顶向下)

class Solution {

private:

    int recursion (int n){

        if(n==1||n==2)

            return n;

        return recursion(n-1)+recursion(n-2);

    }

public:

    int climbStairs(int n) {

        //递归

        return recursion(n);

    }

};

上述代码提交后会超时,因为有大量重叠子问题,会导致有重复计算而超时

我们可以建立一个备忘录来解决(记忆化搜索,自上而下)

如果能自上而下的解决问题,那么一定可以自下而上的解决

记忆化搜索(自顶向下)

#include<vector>

class Solution {

private:

    vector<int> memo;

    int recursion(int n){

        if(n==1|n==2)

            return n;

        if(memo[n]==-1)

            memo[n]=recursion(n-1)+recursion(n-2);

        return memo[n];

    }

public:

    int climbStairs(int n) {

    //备忘录

    //memo范围是[0,n]

    memo=vector<int>(n+1,-1);

    return recursion(n);

    }

};

动态规划(自底向上)

#include<vector>

class Solution {

public:

    int climbStairs(int n) {

        vector<int> memo(n+2,-1);

        memo[1]=1;

        memo[2]=2;

        for(int i=3;i<=n;i++){

            memo[i]=memo[i-1]+memo[i-2];

        }

        // memo[0]=1;

        // memo[1]=1;

        // for(int i=2;i<=n;i++){

        //     memo[i]=memo[i-1]+memo[i-2];

        // }

        return memo[n];

    }

};

343. 整数拆分

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

递归(自顶向下)

暴力解法:回溯遍历将一个数分割的所有可能 O(2^n)指数级别

#include<iostream>

using namespace std;

class Solution {

private:

    int max3(int a,int b,int c) {

        return max(a, max(b, c));

    }

    //将n进行分割(至少分两部分),可以获得的最大乘积

    int breakInteger(int n) {

        if (n == 1)

            return 1;

        int MAX;

        //只看第一层

        for (int i = 1; i <= n - 1; i++)

            MAX=max3(MAX,i*breakInteger(n - i),i*(n-i));

        return MAX;

    }

public:

    int integerBreak(int n) {

        return breakInteger(n);

    }

};

提交代码显示超时,因为我们有大量的重叠子问题,可以建立一个vector<int>来记录已经计算过的值,避免重复计算

记忆化搜索(自顶向下)

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

    vector<int> memo;

    int MAX;

    int max3(int a,int b,int c) {

        return max(a, max(b, c));

    }

    //将n进行分割(至少分两部分),可以获得的最大乘积

    int breakInteger(int n) {

        if (n == 1)

            return 1;

        if (memo[n] != -1)//说明已经计算过

            return memo[n];

        //只看第一层

        for (int i = 1; i <= n - 1; i++)

            MAX=max3(MAX,i*breakInteger(n - i),i*(n-i));//因为至少分割成两部分,那么遗漏了i*(n-i)

        memo[n] = MAX;

        return MAX;

    }

public:

    int integerBreak(int n) {

        //初始化备忘录,[0,n]都为-1

        memo=vector<int>(n+1,-1);

        return breakInteger(n);

    }

};

动态规划(自底向上)

O(n^2)

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

    vector<int> memo;

    int MAX;

    int max3(int a,int b,int c) {

        return max(a, max(b, c));

    }

public:

    int integerBreak(int n) {

        //数组元素的含义:memo[i],表示将数字i分割后(至少两部分)得到的最大乘积

        vector<int> memo(n + 1, -1);

        //初始值

        memo[1] = 1;

        //从底向上(从2开始,循环到n,因为我们要求memo[n],所以必然要先求出其最优子结构)

        for (int i = 2; i <= n; i++)

            //求解memo[i]

            for (int j = 1; j <= i - 1; j++)

                memo[i] = max3(memo[i], j * memo[i - j], j * (i - j));

        return memo[n];

    }

};


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
500万AI人才缺口「高校造」,科技公司培养AI应用人才的新模式
在 500 万 AI 人才紧缺的当下,数字蓝领和 AI 应用层面的人才最缺,其次是算法人才和科研人才。高校作为承载人才出口的重要角色,在人工智能和机器人企业优必选科技的助力下,AI 人才高校造的局势正在打开。
4 0
重估「AI国家队」云从:步入寒冬还是万物生长
在外患内忧的境地中,属于 AI 的狂热浪潮已经过去,技术进入更为务实的成长区间,从此 AI 将更广泛的融入生活。通过这场世纪对话,我们发现这家从广州而起的 AI 独角兽,正逐渐成为一个时代的标志。
7 0
「人工智能第一股」依图科技冲刺科创板,按下国产芯片加速键
从招股书看,已经很难用「计算机视觉」这个标签来定义依图。他是以人工智能芯片技术和算法技术为核心,研发及销售包含人工智能算力硬件和软件在内的人工智能解决方案。 在对标公司方面,依图招股书选取的是 Google、华为、NVIDIA、寒武纪、海康威视、科大讯飞六家公司作为同行业可比公司。
7 0
让自动驾驶撞墙,刷别人的脸付账:最新的AI安全漏洞让我们开了眼界
那些专家们曾经担心过的 AI 算法漏洞是可以实现的,没想到过的也可以实现。
4 0
Photoshop把AI论文demo打包实现了:照片上色、改年龄、换表情只需要点点鼠标
我们见过很多神经网络上色、换表情、修改年龄的研究和应用,但它们往往只存在于 GitHub 上,距离「人人能用」还有一段距离。但最近,推出 Photoshop 的 Adobe 这次终于有所表示了:你们论文里的效果,我们打包实现了。
4 0
美团开店首秀:全自动拣货,95%订单全无人配送
敢为人先的美团,也开始学起亚马逊开店了,不过这是第一家由骑手经营的智慧门店。以无人微仓和无人配送发展「前置仓 + 即时配送」的新型零售门店,首次落地首钢园,为 3km 半径内智慧园区的生活服务提供新的机会。
5 0
SpringBoot 如何在日志中增加 trace id 用于链路追踪
SpringBoot 如何在日志中增加 trace id 用于链路追踪
7 0
阿里云天池Apache Spark落幕:AI医疗进入落地实践深水期,达摩院如何用生态破局?
一次疫情,让阿里达摩院医疗 AI 团队一战成名。 他们利用整个假期,疫情爆发初期迅速将技术落地,率先在「郑州小汤山」落地的第一套 CT 影像识别系统代码和图片已经被分别收藏在中国国家博物馆和中国科技馆。 疫情之后,达摩院医疗 AI 产品迅速进入落地阶段,成长与痛点并存。 面对技术落地面临的普遍困境,达摩院以「数字人体」系列比赛为抓手,逐渐搭建起行业生态。
4 0
原滴滴AI Labs负责人叶杰平正式加入贝壳找房
滴滴出行原副总裁叶杰平的去向终于尘埃落定。
6 0
+关注
62
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载