当前位置：网站首页>动态规划111

动态规划111

2022-06-26 19:43:00 【江江春】

基础问题

背包问题(带限制的取集合，求价值或种类)
打家劫舍
股票问题
子序列问题

基本解法

dp数组，以及下标含义
递推公式
dp数组初始化
遍历顺序（一维数组一层，二维数组两层）
1. 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
2. 若是01背包，则从后往前，否则从前往后
打印数组（debug）

思路:

关键是自底向上思考

首先考虑步骤，

比如背包问题，步骤就是一个一个放入物品，怎样放入物品才是最优解。每一个物品有两步放，不放。观察全局决定放还是不放。（从头往后退看是否要放入）

再比如上台阶问题，步骤就是跨步，跨几步是最优解，每次可以跨一步或者两步。观察全局决定跨一步还是两步。（从头往后退，每次是一步最优还是两步最优）

凡是一步一步地问题,下个状态有依赖于上一个状态的问题考虑用动态规划.首先从最后一步开始,想象出最后一步到终点的状态需要哪些操作

动态规划数组的值一定是答案

背包问题(求价值问题)

究其根本是有限制与求价值的取集合。背包容量与物品重量构成限制，物品价值即为价值。

二维写法：

// 1 dp数组下标及自身含义
    // dp[i][j]
    //i:从0 -i号商品 j：背包容量
    //ij:从0-i任取，放入j中的最大价值
// 2 递推公式
    // dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+value)
// 3 dp数组初始化
    //实际情况
// 4 遍历顺序
    //先背包在物品


    // 
function bagProblem(weight,value,volume){
    let count=weight.size+1
    // 1 定义dp
    const dp=[]

    // 3 初始化dp数组
    for (let j = volume; j >= weight[0]; j--) {
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }


    // 4 遍历顺序
    for(let i=1;i<weight.length;i++){
        for(let j=0;j<=volume;j++){
            if(j<weight[i]){
                dp[i][j]=dp[i-1][j]
            }else{
                // 2 递推公式
                dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
}

压缩，一维写法

由上图可以得出dp[i][j]部分是由dp[i-1][j]拷贝而来，完全可以省略空间，用一维数组代替

1、dp定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2、递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

此时dp[j]有两个选择，一个是取自己dp[j]，一个是取dp[j - weight[i]] + value[i]，指定是取最大的，毕竟是求最大价值，

3、dp数组初始化

初始化为0

4、遍历顺序

从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 1 dp数组下标及自身含义
    // dp[j]:容量为j时的最大价值
    //j:容量
// 2 递推公式
    // dp[j]=max(dp[j],dp[j-w[i]]+value)
    // 这里的dp[j]其实是二维数组中上一层的复制，即上一个物品不放时的价值
// 3 dp数组初始化
    //都为0
// 4 遍历顺序
    //先背包在物品
    // 倒序遍历背包，防止上层状态被覆盖


function bagProblem(weight,value,volume){
    let count=weight.size
    // 1 定义dp
    const dp=[]

    // 3 初始化dp数组
    // 
    for(let i=0;i<volume;i++){
        dp[i]=0
    }

    // 4 遍历顺序
    for(let i=0;i<weight.length;i++){
        // ps：大于weight，小于weight直接放不进去继承上一层状态（直接不放入）
        for(let j=volume;j>=weight[i];j--){
            // 2 递归公式
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
        }
    }
}