动态规划

基于背包问题复习一下动态规划

一.big picture

1. 基本概念

每次决策都依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的。这种多阶段最优化解决问题的过程就称为动态规划。

2. 基本思想与策略

将待求解问题分解问若干阶段，按照顺序求解子阶段，前一阶段的解，为后一阶段提供信息。在求解子阶段的时候，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解了。对于每个子问题只求解一次，将其保存在二维数组中。

3. 适用的情况

(1) 最优化原理：如果问题的最优解包含的子问题的解也是最优，（最优由最优推导而来）就称该问题有最优子结构。

(2) 无后效性：当前阶段不会受以后决策的影响，只和前状态有关。

(3) 有重叠的子问题：子问题之间是不独立的，一个子问题会在下一个阶段使用到。

4. 求解的基本步骤

(1) 划分阶段：按照问题的时间和空间，把问题划分为多个阶段，注意划分后的阶段一定是有序的或者可排序的。

(2) 确定状态和状态变量

(3) 确定决策和状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。根据相邻两个阶段的状态之间的关系来确定决策办法和状态转移方程。

(4) 寻找边界/终止条件

分析最优解的性质，递归定义最优解，自底向上或自顶向下计算求解，构造问题最优值。

5. 动态规划三要素：

(1) 问题的阶段

(2) 每个阶段的状态

(3) 状态间的递推关系

确定三要素后，整个求解过程就可以用一个最优决策来描述，一个二维表，行表示决策阶段，列表示问题状态（问题在某个阶段某个状态下的最优值）

$$f(n,m)=max \{f(n - 1,m) , f(n - 1, m - w[n] + P(n,m)\}$$

6.算法框架

input w[n] v[n] m(状态):
for j = 1 -> m:
truedp[n][j] = 初始值；
for i = 1 -> n
truefor j = w[i] -> m:
truetruedp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

相关题目

最长回文字符串

https://leetcode.com/problems/longest-palindromic-substring/description/

描述:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

样例:

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

解法:

为什么可以用动态规划：最长回文字符串的子串也是回文字符串。且小的长度的回文字符串不受长的的影响，有叠加子问题。

在最长回文字符串里，我按照回文字符串的长度小大到大去遍历s。状态矩阵dp是记录在长度为i时，结尾处index为j的子串是不是回文字符串。

public String longestPalindrome(String s) {
        //行为长度，列为index
        if(s == null || s.length() == 1)return s;
        boolean[][] dp = new boolean[s.length() + 1][s.length()];
        for(int i = 0; i < s.length(); i++){
            dp[0][i] = true;
            dp[1][i] = true;
           
        }
        String result = s.substring(0,1);
        for(int i = 2; i < s.length() + 1; i++){
            for(int j = i - 1 ;j < s.length(); j++){
                if(s.charAt(j) == s.charAt(j - i + 1) && dp[i - 2][j - 1]){
                    dp[i][j] = true;
                    result = s.substring(j - i + 1, j + 1);
                }
            }
        }
        return result;
    }

最长公共子序列

http://www.lintcode.com/zh-cn/problem/longest-common-subsequence/

描述

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

说明

最长公共子序列的定义：

• 最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

样例

给出“ABCD” 和 “EDCA”，这个LCS是 “A” (或 D或C)，返回1

给出 “ABCD” 和 “EACB”，这个LCS是“AC”返回 2

解法:

ABCD和EACB的最长公共子序列取决于ABC和EACB，ABCD和EAC(如果ABCD和EACB最后一位不相等)以及ABC和EAC(如果ABCD和EACB最后一位相等)。

构建动态规划状态矩阵dp，行为String A的子串的长度，列为String B的子串长度。

public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if(A == null || B == null)return 0;
        int m = A.length(), n = B.length();
    	//行为String A的子串的长度，列为String B的子串长度。
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // dp[i][j] = dp[]
                if(A.charAt(i - 1) == B.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = Math.max(dp[i][j - 1],dp[i-1][j]);
                }
                max = Math.max(dp[i][j],max);
            }
        }
        return max;
    }

1.最基础的背包问题

http://www.lintcode.com/zh-cn/problem/backpack/

描述

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

样例

如果有4个物品[2, 3, 5, 7]

如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。

如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。

函数需要返回最多能装满的空间大小。

建立动态规划数据dp[A.lenght][m + 1].

dp[i][j]为当背包总重量为j且有前i个物品时，背包最多装满dp[i][j]的空间。
状态转移方程为：dp[i][j] = Math.max(dp[i - 1][j - A[i]] + A[i], dp[i-1][j]);

即不放入 A[i]: dp[i-1][j];

放入A[i] : dp[i - 1][j - A[i]];(要考虑能不能放入A[i])

start	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5	j = 6	j = 7	j = 8	j = 9	j = 10	j = 11
i = 0 (A[0]=2)	0	0	2	2	2	2	2	2	2	2	2	2
i = 1 (A[1]=3)	0	0	2	3	3	5	5	5	5	5	5	5
i = 2 (A[2]=5)	0	0	2	3	3	5	5	7	8	8	10	10
i = 3 (A[3]=7)	0	0	2	3	3	5	5	7	8	9	10	10

代码

 /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
public int backPack(int m, int[] A) {
        // write your code here
        if(A == null || m == 0)return 0;
        int[][] dp = new int[A.length][m + 1];
        //状态方程dp[i][j] = max(dp[i-1][j], dp[i - 1][j - A[i]]  + A[i])
        //初始化矩阵 初始化dp[0][j]的值，因为在转移方程中i是从1开始。
    	for(int j = m; j >= 0; j--){
            if(j >= A[0])dp[0][j] = A[0];
            else break;
        }
        for(int i = 1; i < A.length; i ++){
            for(int j = 0;  j < m + 1; j++){
                if(j >= A[i]){
                    //取上一次的状态
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]);
                }
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[A.length - 1][m];
    }

优化

观察上面的代码，其实我们只需要i-1行的信息去更新第i行的信息。因此很多空间是浪费的。

进一步可以优化为O(m)的空间，我们需要的是对所有物品在m背包内能放入的最大重。因此其实只需要上面dp[][]中的最后一行。f[j] = Max(f[j],f[j-A[i]]+A[i]) 这里就相当于对上面的矩阵进行了压缩

// O(m) 空间复杂度的解法
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        int f[] = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j >= A[i]; j--) {
                //为什么要倒序，因为原来二维矩阵中是依赖上一次的状态，而对于一维矩阵，若从前往后循环则变成依赖本次循环而非上次循环。
                f[j] = Math.max(f[j], f[j - A[i]] + A[i]);
            } 
        }
        return f[m];
    }
}

2. 最基础的0-1背包问题（有价值）

http://www.lintcode.com/zh-cn/problem/backpack-ii/

描述

给出n个物品的体积C[i]和其价值W[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

样例

对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话，最大能够装入的价值为9。

与上面的问题类似，可以简单认为上面的问题是单位价值为1的物品。转移方程如下：

$$F[i,v] = max{F[i − 1,v],F[i − 1,v − Ci] + Wi}$$

伪代码

for i = 1 to N
truefor v = Ci to V
truetrueF[i,v] ← max{F[i − 1,v],F[i − 1,v − Ci] + Wi}

空间复杂度优化

现在空间复杂度为$O(MN)$ ，和上一步一样我们可以优化为$O(M)$. 先考虑上面讲的基本思路如何实现，肯定是有一个主循环 $i ← 1 . . . N $，每次算出来二维数组 $F[i,0…V ] $的所有值。那么，如果只用一个数组 $F[0…V ]$，能不能保证第 i次循环结束后 $F[v] $中表示的就是我们定义的状态$ F[i,v] $呢?$F[i,v] $是由$ F[i − 1,v] $和$F [i − 1, v − Ci]$ 两个子问题递推而来，能否保证在推 $F [i, v] $时(也即在第 i 次主循环中推 F[v] 时)能够取用 $F[i−1,v] $和$ F[i−1,v−Ci] $的值呢?

事实上，这要求在每次主循环中我们以 $v ← V . . . 0$ 的递减顺序计算 $F [v]$，这样才能保证计算$ F[v]$ 时 $F[v − Ci] $保存的是状态 $F[i − 1,v − Ci]$ 的值。伪代码如下:

for i = 1 to N
trueforv = V to Ci
truetrueF[v] ←max{F[v],F[v−Ci]+Wi}

其中的 $F [v] ← max{F [v], F [v − Ci] + Wi} $一句，恰就对应于我们原来的转移方程，因为现在的 $F [v − Ci]$ 就相当于原来的$ F [i − 1, v − Ci]$。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了$ F [i, v] $由$ F [i, v − Ci] $推导得到，与本题意不符。

参考代码：

public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        if(m == 0 || A == null || V == null) return 0;
        int[] f = new int[m + 1];
        for(int i = 0; i < A.length; i++)
        {
            for(int bag = m; bag >= A[i]; bag--){
                f[bag] = Math.max(f[bag], f[bag - A[i]] + V[i]);
            }
        }
        return f[m];
    }

初始化的细节

有的背包问题有时要求的是把背包装满时得到的最大值，有时则不用装满（如上例）。两种的区别在于初始化数组时的不同。在初始化时除了 $F[0]$ 为 0，其它$F [1..V ]$ 均设为$ −∞$，这样就可以保证最终得到的$ F [V ] $是一种恰好装满背包的最优解。
可以这样理解:初始化的 $F$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为$ 0 $的背包可以在什么也不装且价值为 $0 $的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 $-∞ $了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 $0$，所以初始时状态的值也就全部为$ 0$了。

http://www.lintcode.com/zh-cn/problem/backpack-v/

描述

给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次

样例

给出候选物品集合 [1,2,3,3,7] 以及 target 7

结果的集合为:
[7]
[1,3,3]

返回 2

代码

public int backPackV(int[] nums, int target) {
        // write your code here
        Arrays.sort(nums);
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int bag = target; bag >= nums[i]; bag--){
                dp[bag] += dp[bag - nums[i]];
            }
        }
        return dp[target];
    }

3. 完全背包问题

描述

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci，价值是 Wi。求解:将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2件……直至取$ ⌊V /Ci⌋$ 件等许多种。

如果仍然按照解 01 背包时的思路，令$ F[i,v] $表示前 i 种物品恰放入一个容量为 v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样:

$$F[i,v]=max{F[i−1,v−kC_i]+kWi \ \ \ \ 0≤kC_i ≤v}$$

转换为0-1背包问题求解

01 背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为 01 背包问题来解。

最简单的想法是，考虑到第 i 种物品最多选 $⌊V /Ci⌋ $件，于是可以把第 i 种物品转化为$ ⌊V /Ci⌋$ 件费用及价值均不变的物品，然后求解这个 01 背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为 01 背包问题的思路:将一种物品拆成多件只能选 0 件或 1 件的 01 背包中的物品。

更高效的转化方法是:把第 i 种物品拆成费用为$ C_i2^k$、价值为 $W_i2^k$ 的若干件物品，其中 k 取遍满足 $C_i2^k ≤ V$ 的非负整数。

这是二进制的思想。因为，不管最优策略选几件第 i 种物品，其件数写成二进制后，总可以表示成若干个 2k 件物品的和。这样一来就把每种物品拆成 $O(log ⌊V /C_i⌋)$ 件物品，是一个很大的改进。

$O(VN)$求解

伪代码

F [0..V ] = 0
for i = 1 to N
truefor v = Ci to V
truetrueF[v] = max(F[v],F[v−Ci]+Wi)

这种方法和0-1背包的方法，只有第二重循环不同。0-1背包的第二重循环是从V -> Ci, 而完全背包则是从Ci -> V。 在0-1背包中我们希望每一步i 只依赖于上一步i - 1的状态，即为了保证每个物品只选一次。因此循环是从尾开始。而在完全背包中，我们可以选一件物品无数次，因此我们依赖于当前次的状态。因此我们应该从头开始循环。

重复选择+不同排列+装满可能性总数

http://www.lintcode.com/zh-cn/problem/backpack-vi/

描述

给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。

样例

给出 nums = [1, 2, 4], target = 4
可能的所有组合有：

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]

返回 6。

代码

public int backPackVI(int[] nums, int target) {
        // write your code here
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int bag = 0; bag <= target; bag++){
            for(int num : nums){
                if(num <= bag) dp[bag] += dp[bag - num];
            }
        }
        return dp[target];
    }

​
​