区块链技术博客
www.b2bchain.cn

算法-动态规划

这篇文章主要介绍了算法-动态规划,通过具体代码讲解6039并且分析了算法-动态规划的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-动态规划。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6039。具体如下:

算法 动态规划

算法

发布日期:   2019-12-02
文章字数:   2.5k
阅读时长:   11 分
阅读次数:  

动态规划:背包型

数组开n+1,背包关键就是看最后一步。

1、01背包–求max

LintCode 92: Backpack

【问题】在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]

【分析】从最后一步出发,最后一个物品放还是不放。有两种情况

  • 前n-1个物品能拼出重量 w,那么n个物品也能拼出重量w
  • 前n-1个物品能拼出重量 w - A[n-1],再加上最后一个物品 A[n-1] 拼出w

【状态转移】

  • dp[i][w]表示能否用前i个物品拼出重点w,可以用int数组,也可以用boolean数组,
  • dp[i][j] = max{dp[i-1][j], dp[i-1][j - A[n-1]] + A[i-1]}(int数组)放还是不放
  • dp[i][j] = dp[i-1][w] or dp[i-1][j - A[i-1]](boolean数组)
//int型写法 public static int backPack2(int m, int[] A) {         int n = A.length;         int[][] dp = new int[n + 1][m + 1];         for (int i = 1; i <= n; i++) {             for (int j = 0; j <= m; j++) {                 //不放                 dp[i][j] = dp[i - 1][j];                 //放                 if (j >= A[i - 1]) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);                 }             }         }         return dp[n][m];     } //boolean型写法 public int backPack(int m, int[] A) {         int n = A.length;   //物品个数         boolean[][] dp = new boolean[n + 1][m + 1];         dp[0][0] = true;         for (int i = 1; i <= m; i++) {             dp[0][i] = false;         }          for (int i = 1; i <= n; i++) {             //首先初始化dp[i][0]             for (int j = 0; j <= m; j++) {                 //不放                 dp[i][j] = dp[i - 1][j];                 //放                 if (j >= A[i - 1]) {                     // |=,只要有一个为true就是true                     // 放入A[i-1]的情况就是看j-A[i-1]这个容量下是不是为true,如果为true,那么就是dp[i][j]为true,否则就是看dp[i-1][j]是否为true                     dp[i][j] |= dp[i - 1][j - A[i - 1]];                 }             }         }         int res = 0;         for (int i = m; i >= 0; i--) {             if (dp[n][i] == true) {                 res = i;                 break;             }         }         return res;     }

优化成一维

public int backPack(int m, int[] A) {         int f[] = new int[m + 1];         for (int i = 0; i < A.length; i++) {              //从后往前更新           //下面的f[j - A[i]],j - A[i]严格小于j,j是从小到大枚举的           //也就是在第i层已经算过了,等价于f[i][j-A[i]]           //那么我们从大到小更新,算f[j],f[j - A[i]]其实是还没有被更新过,它存的是第i-1层的,这就对了             for (int j = m; j >= A[i]; j--) {                   //不放和放,不放就是它自身                 f[j] = Math.max(f[j], f[j - A[i]] + A[i]);             }          }         return f[m];     }

2、01背包–求数量

LintCode 563: Backpack V

【问题】给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。注意:每一个物品只能使用一次。

【分析】需要求出有多少种组合能组合成target,对于最后一个物品,有放和不放两种选择。

  • 第一种:使用前n-1个物品拼出target
  • 第二种:前n-1个物品能拼出target - nums[i],再加上nums[i],拼出target
  • 拼出target的方式 = 不放+放,即dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]]
  • 如果知道有多少种方式拼出0、1、2…对于有多少种方式拼出target也就知道答案了。

常规写法,时间复杂度O(n*Target)

public static int backPackV1(int[] nums, int target) {         int n = nums.length;         if (n == 0) {             return 0;         }          int[][] dp = new int[n + 1][target + 1];    //dp[i][j]表示前i个数字有多少种方式拼出数字j         dp[0][0] = 1;   //0个物品有一种方式拼出重量0         //初始化         for (int i = 1; i <= target; i++) {             dp[0][i] = 0;         }         for (int i = 1; i <= n; i++) {             //拼出几             for (int j = 0; j <= target; j++) {                 //不放                 dp[i][j] = dp[i - 1][j];                 //放                 if (j >= nums[i - 1]) {                          dp[i][j] += dp[i - 1][j - nums[i - 1]];                 }             }         }         return dp[n][target];     }

第一步优化:利用滚动数组

public static int backPackV3(int[] nums, int target) {         int n = nums.length;         if (n == 0) {             return 0;         }         int[][] dp = new int[2][target + 1];         dp[0][0] = 1;         for (int i = 1; i <= target; i++) {             dp[0][i] = 0;         }         int old = 0, now = 0;         for (int i = 1; i <= n; i++) {             old = now;;             now = 1 - now;             for (int j = 0; j <= target; j++) {                 //不放                 dp[now][j] = dp[old][j];                 //放                 if (j >= nums[i - 1]) {                     dp[now][j] += dp[old][j - nums[i - 1]];                 }             }         }         return dp[now][target];     }

第二步优化:优化成一行。原本是 老值 + 老值 = 新值,如果正着更新,可能会出现 老值 + 新值,所以需要倒着更新

dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]],新值 = 两个老值加起来

public static int backPackV2(int[] nums, int target) {         int n = nums.length;         if (n == 0) {             return 0;         }         int[] dp = new int[target + 1]; //和总称重有关         //init:相当于dp[0][0] = 1         dp[0] = 1;         //init:dp[0][1] = dp[0][2] = ... = 0         for (int i = 1; i <= target; i++) {             dp[i] = 0;         }          for (int i = 1; i <= n; i++) {             //reverse             for (int j = target; j >= 0; j--) {                 if (j >= nums[i - 1]) {                     //old + old ==> new old1 = dp[j],old2 = dp[j - nums[i - 1]],new就是直接覆盖                     dp[j] += dp[j - nums[i - 1]];                 }             }         }         return dp[target];     }

3、LintCode 564: Backpack VI

【问题】给出一个都是正整数的数组 nums,其中没有重复的数。从中找出所有的和为 target 的组合个数。注意一个数可以在组合中出现多次,数的顺序不同则会被认为是不同的组合。

【分析】这个题和Backpack V的区别是每个物品可以使用多次,且组合中数字可以按照不同顺序,比如1+1+2与1+2+1算是两种情况,这就导致不能按照物品顺序来处理。依旧是关注最后一步,最后一步物品重量是K,那么前面物品构成重量target-K,需要关注最后一个加进来的是谁。

  • 如果最后一个物品重量是A0, 则要求有多少种组合能拼成 Target – A0
  • 如果最后一个物品重量是A1, 则要求有多少种组合能拼成 Target – A1
  • ……
  • 如果最后一个物品重量是An-1, 则要求有多少种组合能拼成 Target – An-1

【状态转移方程】dp[i]代表有多少种组合能拼出重量i,则dp[i] = dp[i-A[0]] + dp[i-A[1]] +...+ dp[i-A[n-1]]

【初始条件】dp[0] = 1,有1种组合能拼出0

public int backPackVI(int[] nums, int target) {         int n = nums.length;         int[] dp = new int[target + 1];         dp[0] = 1;          //对于能拼出的i         for (int i = 1; i <= target; i++) {             //初始化能拼出i的情况为0种             dp[i] = 0;               //遍历所有数字             for (int j = 0; j < n; j++) {                 if (i >= nums[j]) {                     dp[i] += dp[i - nums[j]];                 }             }         }         return dp[target];     }

4、LintCode 125: Backpack II

【问题】有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。问最多能装入背包的总价值是多大?注意:每个物品只能取一次,物品不能切分。

public int backPackII(int m, int[] A, int[] V) {         int n = A.length;         int[][] dp = new int[n + 1][m + 1];         //初始化         for (int i = 0; i <= m; i++) {             dp[0][i] = 0;         }         int res = Integer.MIN_VALUE;         for (int i = 1; i <= n; i++) {             for (int j = 0; j <= m; j++) {                 //不放                 dp[i][j] = dp[i - 1][j];                   //放                 if (j >= A[i - 1]) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);                 }                 res = Math.max(res, dp[i][j]);             }         }         return res;     }

5、完全背包

LintCode 440: Backpack III

【问题】将Backpack II的物品改为无穷多个,背包最大承重m,求能带走的最大价值。

  • 输入:4个物品,重量为2, 3, 5, 7,价值为1, 5, 2, 4. 背包最大承重是10
  • 输出:15

【分析】Ai-1有无穷多个,可以用1个、2个…在这里可以把物品变为种类,这边状态转移方程变为

  • f[i] [w] = maxk>=0{f[i-1] [w-kAi-1] + kVi-1},表示用前i种物品拼出重量w时的最大总价值,等于用前i-1种物品拼出重量w-kAi-1 时最大总价值,加上k个第i种物品,当k = 0和1时,就可以直接用在Backpack II 中了。

把这个式子展开,如下

算法-动态规划

可以优化

算法-动态规划

什么意思呢

假设Ai-1 = 2,Vi-1 = x

f[i] [5] = max{ f[i-1] [5], f[i-1] [3] + x, f[i-1] [1] + 2x }

f[i] [7] = max{ f[i-1] [7], f[i-1] [5] + x, f[i-1] [3] + 2x, f[i-1] [1] + 3x }

这样算了重合的部分,不是我们想要的

// 只需要把Backpack II中关键一行改为 // dp[i][j] = Math.max(dp[i][j],dp[i][j - A[i-1]] + V[i-1])    public int backPackII(int m, int[] A, int[] V) {         int n = A.length;         int[][] dp = new int[n + 1][m + 1];         //初始化         for (int i = 0; i <= m; i++) {             dp[0][i] = 0;         }         int res = Integer.MIN_VALUE;         for (int i = 1; i <= n; i++) {             for (int j = 0; j <= m; j++) {                 //不放                 dp[i][j] = dp[i - 1][j];                   //放                 if (j >= A[i - 1]) {                     dp[i][j] = Math.max(dp[i][j],dp[i][j - A[i-1]] + V[i-1]);                 }                 res = Math.max(res, dp[i][j]);             }         }         return res;     }

可以优化到一维,这边的细节是:用的不是两个old值,而是old+new,可以只开一个数组,old+new去覆盖本来的old,这就需要时从前往后来,而不是逆序,如图

算法-动态规划

public int backPackIII(int m, int[] A, int[] V) {         int n = A.length;         int[] dp = new int[m + 1];         dp[0] = 0;         int res = Integer.MIN_VALUE;         for (int i = 1; i <= n; i++) {             for (int j = 0; j <= m; j++) {                 if (j >= A[i - 1]) {    //上面改成j直接从A[i-1]出发更好                   //old = dp[j],new = dp[j - A[i - 1] + V[i - 1]],加起来覆盖本来的old                   //old相当于原来的dp[i-1][j],dp[j - A[i - 1]相当于dp[i][j - A[i - 1]                   //这边就不需要倒着更新,因为和二维的状态转移方程是一致的,我们需要的就是第i层的                   //这里不动看下01背包那边的注释就懂了                     dp[j] = Math.max(dp[j], dp[j - A[i - 1] + V[i - 1]]);                 }                 res = Math.max(res, dp[j]);             }         }         return res;     }

TBD:多重背包(这个优化思想比较巧妙)、分组背包


算法 动态规划

序列型dp就是序列+状态,直接看几个例子。 1、LintCode 515 Paint House【问题】这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻
2019-12-04 算法
动态规划:划分型划分型动态规划就是给定长度为N的字符串,需要划分成若干段,段数不限,每一段满足一定的性质。在学校oj中做过的书本分发、漆狗屋这种就属于划分型。开数组也是开n+1 1、Lintcode 512 解码方法【问题】有一个消息包含A
2019-12-02 算法

本文地址https://www.b2bchain.cn/?p=6039

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-动态规划
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们