【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型

目录

背包问题概述

01 背包问题

01背包⭐⭐ 

【算法原理】

第一问

第二问

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

分割等和子集⭐⭐

【算法原理】 

对于类01背包问题

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

目标和⭐⭐

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

最后一块石头的重量Ⅱ⭐⭐⭐ 

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

背包问题概述

        背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题。

        问题可以描述为：给定⼀组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

根据物品的个数，分为如下几类：
  • 01 背包问题：每个物品只有⼀个。
  • 完全背包问题：每个物品有无限多个。
  • 多重背包问题：每件物品最多有 si 个。
  • 混合背包问题：每个物品会有上⾯三种情况......。
  • 分组背包问题：物品有 n 组，每组物品⾥有若干个，每组里最多选⼀个物品。
其中上述分类里面，根据背包是否装满，又分为两类：
  • 不一定装满背包
  • 背包一定装满
优化方案：
  • 空间优化 - 滚动数组
  • 单调队列优化
  • 贪心优化
根据限定条件的个数，⼜分为两类：
  • 限定条件只有⼀个：比如体积 -> 普通的背包问题
  • 限定条件有两个：比如体积 + 重量 -> ⼆维费用背包问题
根据不同的问法，又分为很多类：
  • 输出方案
  • 求方案总数
  • 最优方案
  • 方案可行性
        因此，背包问题种类非常繁多，题型非常丰富，难度也是非常难以捉摸。但是，尽管种类非常多，都是从 01 背包问题演化过来。所以： ⼀定要把 01 背包问题学好 。

01 背包问题

01背包⭐⭐ 

【模板】01背包_牛客题霸_牛客网 (nowcoder.com)

【算法原理】

第一问

#：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ]表示：从前 i 个物品中挑选，总体积不超过 j ，所有选法中，能挑选出来的最大价值。（也看出来划了杠，看似很完美，但其实是错的），因为一个背包是有体积的，有体积为关键的背包仅仅看第几个物品是没用的。

        我们需要将背包的体积也需要包含进去，d[ i ][ j ]表示：从前 i 个物品中挑选，总体积不超过 j ，所有选法中，能挑选出来的最大价值。

#：状态转移方程：

线性 dp 状态转移方程分析方式，⼀般都是根据「最后⼀步」的状况，来分情况讨论：
  • 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j，此时 dp[ i ][ j ] = dp[ i - 1 ][ j ]。
  • 选择第 i 个物品：那么我就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[ i ] 的物品。此时 dp[ i ][ j ] = dp[ i - 1 ][ j - v[ i ] ] + w[ i ]。但是这种状态不⼀定存在，因此需要特判⼀下。

        综上，状态转移方程为：dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - v[ i ] ] + w[ i ])。

#：初始化：

       我们多加⼀行，方便我们的初始化，此时仅需将第⼀行初始化为 0 即可。因为什么也不选，也能满足体积不小于 j 的情况，此时的价值为 0 。

#：填表顺序：

        根据「状态转移方程」，我们仅需「从上往下」填表即可。

#：返回值：

        根据「状态表示」，返回 dp[n][V] 。 

第二问

#：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示：从前 i 个物品中挑选，总体积「正好」等于 j ，所有的选法中，能挑选出来的最⼤价值。

#：状态转移方程：

  • dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - v[ i ] ] + w[ i ]) 。

        但是在使用 dp[ i - 1 ][ j - v[ i ] ] 的时候，不仅要判断 j >= v[ i ] ，⼜要判断 dp[ i - 1 ][ j - v[ i ] ] 表示的情况是否存在，也就是 dp[ i - 1 ][ j - v[ i ] ] != -1 。

#：初始化：

我们多加一行，方便我们的初始化：

  • 第一个格子为 0 ，因为正好能凑齐体积为 0 的背包。
  • 但是第一行后面的格子都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。

#：填表顺序：

        根据「状态转移方程」，我们仅需「从上往下」填表即可。

#：返回值：

        由于最后可能凑不成体积为 V 的情况，因此返回之前需要「特判」⼀下。

C++ 算法代码

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory.h>
using namespace std;

int main()
{
    int n = 0, V = 0;
    cin >> n >> V;
    vector<pair<int, int>> val;
    val.reserve(n + 1);
    val.push_back(make_pair(0, 0));
    for (int i = n; i > 0 ; i--) {
        int v = 0, w = 0;
        cin >> v >> w;
        val.push_back(make_pair(v, w));
    }

    // 背包不满的时候的最大价值
    // 1、创建dp表
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));

    // 2、初始化 

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < V + 1; j++)
        {
            dp[i][j] = dp[i - 1][j];

            if (j >= val[i].first)
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << dp[n][V] << endl;


    // 背包满的时候的最大价值
    // 1、创建dp表
    fill(dp.begin(), dp.end(), vector<int>(V + 1, 0));

    // 2、初始化
    for (int i = 1; i < V + 1; i++)
        dp[0][i] = -1;

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < V + 1; j++)
        {
            dp[i][j] = dp[i - 1][j];

            if (j >= val[i].first && dp[i - 1][j - val[i].first] != -1)
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

复杂度分析

  • 时间复杂度：O(n*m)，两层for循环。
  • 空间复杂度：O(n*m)。

【空间优化 - 滚动数组】

        首先根据状态方程：dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - v[ i ] ] + w[ i ])，可以发现只是和两行有关，所以我们就可以首先用两个一维数组解决。

        由前一行的两个元素推出需求的位置。根据此我们可以推出一个一维数组解决，只不过有一个问题

        所以，防止在未使用的时候出现被更改的情况，建议以从右往左的顺序进行。

C++ 算法代码

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory.h>
using namespace std;

int main()
{
    int n = 0, V = 0;
    cin >> n >> V;
    vector<pair<int, int>> val;
    val.reserve(n + 1);
    val.push_back(make_pair(0, 0));
    for (int i = n; i > 0 ; i--) {
        int v = 0, w = 0;
        cin >> v >> w;
        val.push_back(make_pair(v, w));
    }

    // 背包不满的时候的最大价值
    // 1、创建dp表
    vector<int> dp(V + 1, 0);

    // 2、初始化 

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = V; j >= val[i].first; j--)
        {
            if (j >= val[i].first)
                dp[j] = max(dp[j], dp[j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << dp[V] << endl;


    // 背包满的时候的最大价值
    // 1、创建dp表
    fill(dp.begin(), dp.end(), -1);

    // 2、初始化
    dp[0] = 0;

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = V; j >= val[i].first; j--)
        {
            if (dp[j - val[i].first] != -1)
                dp[j] = max(dp[j], dp[j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

优化细节：

        因为如果出现 j >= val[i].first；那么 max(dp[j], dp[j - val[i].first] + val[i].second)；没有执行的意义会越界。

        未优化的时候因为需要 dp[ i ][ j ] = dp[i - 1][ j ]；所以必须将第二层循环迭代完成，但是此处由于已经优化为一维数组，所以无需继续迭代。

复杂度分析

  • 时间复杂度：O(n*m)，两个两层for循环。
  • 空间复杂度：O(n)。

分割等和子集⭐⭐

416. 分割等和子集 - 力扣（LeetCode）

​

【算法原理】 

对于类01背包问题

  • 转换：对应的题目提供的要素，时常是需要一个转换过程的（十分重要）。

        重点在于每一个元素的选和不选的问题，也就是01背包关键的地方。

  • 01背包 "模板"：不是说里面的东西都是照抄过来的，而是里面的分析思路 "模板"，根据题目进行一定方式的微调。
        将其转化为「熟悉」的题型，如果数组能够被分成两个相同元素之和相同的子集，那么原数组必须有下面几个性质：
  • 所有元素之和应该是⼀个偶数。
  • 挑选⼀些数，这些数的总和应该等于数组总和的⼀半。

        根据前两个性质，我们可以提前判断数组能够被划分，根据最后⼀个性质，我们发现问题就转化成了「01 背包」的模型：

  • 数组中的元素只能选择⼀次。
  • 每个元素面临被选择或者不被选择的处境。
  • 选出来的元素总和要等于所有元素总和的⼀半。

        其中，数组内的元素就是物品，总和就是背包。 那么我们就可以⽤背包模型的分析方式，来处理这道题。 「不要背」01背包的状态转移方程，我们要记住的是分析问题的模式，用这种分析问题的模式来解决问题。

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，分情况讨论：

  • 不选择 nums[ i ] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j 。根据状态表示：dp[ i ][ j ] = dp[ i - 1 ][ j ]。
  • 选择 nums[ i ] ：这种情况下是有前提条件的，此时的 nums[ i ] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[ i ] 。根据状态表示：dp[ i ][ j ] = dp[ i - 1 ][ j - nums[ i ]]。

        综上所述，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移方程为：dp[ i ][ j ] = dp[ i - 1 ][ j ]；if(nums[ i ] <= j)  dp[ i ][ j ] = dp[ i ][ j ] || dp[ i - 1 ][ j - nums[ i ]]。

#：初始化：

        由于添加了一行一列，因此我们可以先把第一行初始化，第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第一行仅需初始化第⼀个元素 dp[0][0] = true。一列中不放任何元素就可以了，于是第一列全为true。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

        根据「状态表示」，返回 dp[ n ][ aim ] 的值。其中 n 表示数组的大小， aim 表示要凑的目标和。

C++ 算法代码 

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int n = nums.size();
        int sum = 0;
        for(auto val : nums)
            sum += val;

        if(sum % 2) return false;

        // 1、创建dp表
        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));

        // 2、初始化
        for(int i = 0; i < n; i++)
            dp[i][0] = true;

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j < sum + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1])
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }

        // 4、返回值
        return dp[n][sum / 2];
    }
};

【空间优化 - 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int n = nums.size();
        int sum = 0;
        for(auto val : nums)
            sum += val;

        if(sum % 2) return false;

        // 1、创建dp表
        vector<bool> dp(sum + 1, false);

        // 2、初始化
        dp[0] = true;

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = sum + 1; j >= nums[i - 1]; j--)
                dp[j] = dp[j] || dp[j - nums[i - 1]];
        }

        // 4、返回值
        return dp[sum / 2];
    }
};

目标和⭐⭐

494. 目标和 - 力扣（LeetCode）

        用数学知识分析转化成我们常见的「背包模型」的问题。 设我们最终选取的结果中，前面加 + 号的数字之和为 a ，前面加 - 号的数字之和为 b ，整个数组的总和为 sum ，于是我们有：
  • a + b = sum
  • a - b = target
        上面两个式子消去 b 之后，可以得到 a = (sum + target) / 2 也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即可。

【算法原理】 

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，我们有「选择」最后⼀个元素或者「不选择」最后⼀个元素两种策略：
  • 不选 nums[ i ] ：那么我们凑成总和 j 的总方案，就要看在前 i - 1 个元素中选，凑成总和为 j 的方案数。根据状态表示：dp[ i ][ j ] = dp[ i - 1 ][ j ]。
  • 选择 nums[ i ] ：这种情况下是有前提条件的，此时的 nums[ i ] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大，选择它就没有意义呀。那么我们能够凑成总和为 j 的方案数，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[ i ] 。根据状态表示：dp[ i ][ j ] += dp[ i  - 1 ][ j - nums[ i ]]。

         综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移方程为：dp[ i ][ j ] = dp[ i - 1 ][ j ]； if(nums[ i ] <= j)  dp[ i ][ j ] += dp[ i - 1 ][ j - nums[ i ]]。

#：初始化：

        由于需要用到「上一行」的数据，因此我们可以先把第一行初始化。 第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第⼀ 行仅需初始化第⼀个元素 dp[0][0] = 1。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

        根据「状态表示」，返回 dp[ n ][ aim ] 的值。其中 n 表示数组的大小， aim 表示要凑的目标和。

C++ 算法代码 

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto val : nums)
            sum += val;

        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2) return 0;

        int n = nums.size();

        // 1、创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0));

        // 2、初始化
        dp[0][0] = 1;
        
        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 0; j < aim + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1])
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }

        // 4、返回值
        return dp[n][aim];
    }
};

【空间优化 - 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto val : nums)
            sum += val;

        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2) return 0;

        int n = nums.size();

        // 1、创建dp表
        vector<int> dp(aim + 1, 0);

        // 2、初始化
        dp[0] = 1;
        
        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = aim; j >= nums[i - 1]; j--)
                dp[j] += dp[j - nums[i - 1]];
        }

        // 4、返回值
        return dp[aim];
    }
};

最后一块石头的重量Ⅱ⭐⭐⭐ 

1049. 最后一块石头的重量 II - 力扣（LeetCode）

【算法原理】 

先将问题「转化」成我们熟悉的题型。

  • 任意两块石头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就相当于在原始的数据的前面，加上「加号」或者「减号」，是最终的结果最小即可。也就是说把原始的石头分成两部分，两部分的和越接近越好。

  • 又因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越小。
        因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近 sum / 2 ，如果把数看成物品，每个数的值看成体积和价值，问题就变成了「01 背包问题」。

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示在前 i 个元素中选择，总和不超过 j，此时所有元素的「最大和」。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，分情况讨论：
  • 不选 stones[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j 。根据状态表示：dp[ i ][ j ] = dp[ i - 1 ][ j ] 。
  • 选择 stones[i] ：这种情况下是有前提条件的，此时的 stones[ i ] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - stones[ i ] 。根据状态表示：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i - 1 ][ j - stones[ i ]] + stones[ i ]); 。

         综上所述，我们要的是最大价值。因此，状态转移方程为：dp[ i ][ j ] = dp[ i - 1 ][ j ]； if(j >= stones[ i ])  dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i - 1 ][ j - stones[ i ]] + stones[ i ]); 。

#：初始化：

         由于需要用到上一行的数据，因此我们可以先把第一行初始化。 第一行表示「没有石子」。因此想凑成目标和 j ，最大和都是 0 。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

  • 根据「状态表示」，先找到最接近 sum / 2 的最大和 dp[n][sum / 2] 。
  • 因为我们要的是两堆石子的差，因此返回 sum - 2 * dp[n][sum / 2] 。

C++ 算法代码 

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {

        int n = stones.size();
        int sum = 0;
        for(auto val : stones)
            sum += val;
        int half = sum / 2;

        // 1、创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(half + 1, 0));

        // 2、初始化 -- 已经在创建dp表中初始化

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j < half + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= stones[i - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }
        return sum - 2 * dp[n][half];
    }
};

【空间优化 - 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {

        int n = stones.size();
        int sum = 0;
        for(auto val : stones)
            sum += val;
        int half = sum / 2;

        // 1、创建dp表
        vector<int> dp(half + 1, 0);

        // 2、初始化 -- 已经在创建dp表中初始化

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = half; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        }
        return sum - 2 * dp[half];
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/27788.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

常见网络服务器并发模型

常见网络服务器并发模型

近些年&#xff0c;随着互联网的大发展&#xff0c;高并发服务器技术也快速进步&#xff0c;从简单的循环服务器模型处理少量网络并发请求&#xff0c;演进到解决C10K&#xff0c;C10M问题的高并发服务器模型。本文主要以TCP为例&#xff0c;总结了几种常见的网络服务器模型的实…
阅读更多...
Java注解的入门学习

Java注解的入门学习

一、概念 Java注解是一种元数据形式&#xff0c;可以被添加到Java代码中的各种元素&#xff08;类、方法、字段等&#xff09;上&#xff0c;以提供关于这些元素的额外信息。注解是在Java 5中引入的一项特性&#xff0c;它们不直接影响代码的执行&#xff0c;而是提供了一种机…
阅读更多...
本周大新闻｜Vision Pro头显重磅发布；苹果收购AR厂商Mira

本周大新闻｜Vision Pro头显重磅发布；苹果收购AR厂商Mira

本周XR大新闻&#xff0c;上周Quest 3发布之后&#xff0c;本周苹果MR头显Vision Pro正式发布&#xff0c;也是本周AR/VR新闻的重头戏。 ​AR方面&#xff0c;苹果发布VST头显Vision Pro&#xff08;虽然本质是台VR&#xff0c;但以AR场景为核心&#xff09;以及visionOS&…
阅读更多...
【三、网络配置与系统管理】

【三、网络配置与系统管理】

1 网络配置 ifconfig 显示网络接口的配置信息 [rootredis100 ~]# ifconfig ens33: flags4163<UP,BROADCAST,RUNNING,MULTICAST> mtu 1500inet 192.168.10.100 netmask 255.255.255.0 broadcast 192.168.10.255inet6 fe80::f5c3:6a96:fe05:1965 prefixlen 64 scop…
阅读更多...
如何使用Docker实现分布式Web自动化！

如何使用Docker实现分布式Web自动化！

1、前言 顺着docker的发展&#xff0c;很多测试的同学也已经在测试工作上使用docker作为环境基础去进行一些自动化测试&#xff0c;这篇文章主要讲述在docker中使用浏览器进行自动化测试如果可以实现可视化&#xff0c;同时可以对浏览器进行相关的操作。 如果你想学习自动化测…
阅读更多...
畅聊趣坊项目测试报告

畅聊趣坊项目测试报告

文章目录 项目背景项目功能测试计划与设计功能测试自动化测试 测试结果功能测试结果UI自动化测试结果 项目背景 在浏览网站时&#xff0c;发现好多网站开放出聊天的窗口&#xff0c;我们一发送消息就会收到一条消息&#xff0c;好奇这个功能是怎么实现的&#xff0c;最后查阅资…
阅读更多...
cmake 基本使用

cmake 基本使用

目录 CMake都有什么? 使用cmake一般流程为&#xff1a; 1 生成构建系统 使用命令在build外编译代码: cmake基本语法 指定使用最低版本的cmake 指定项目名称 指定生成目标文件的名称 指定C版本 cmake配置文件使用 cmake配置文件生成头文件 版本号定义方法一: 版本号定…
阅读更多...
《操作系统》by李治军 | 实验6 - 信号量的实现和应用

《操作系统》by李治军 | 实验6 - 信号量的实现和应用

目录 一、实验目的 二、实验内容 &#xff08;一&#xff09;用信号量解决生产者—消费者问题 &#xff08;二&#xff09;实现信号量&#xff0c;用生产者—消费者程序检验 三、实验准备 1、信号量 2、多进程共享文件 3、终端也是临界资源 4、原子操作、睡眠和唤醒 …
阅读更多...
C++中string类的常用函数

C++中string类的常用函数

文章目录 默认成员函数常见构造函数(constructor) string类的容量操作size()empty()capacity()reserve()clear()resize() string类对象的访问及遍历操作重载 [ ]begin()end()begin() end() 遍历字符串rbegin()rend()rbegin() rend()反向遍历字符串C11范围for string类对象修改…
阅读更多...
广域网技术——ppp，pppoe

广域网技术——ppp，pppoe

目录 PPP协议概述 PPP协议原理 PPP协议三大组件&#xff1a; PPP链路建立流程 PPP连接建立接口状态&#xff1a; LCP协议报文格式 PPP协议报文格式&#xff1a; 1&#xff0c;链路层建立连接过程 LCP协商过程-正常协商 LCP协商-参数不一致 LCP协商-参数不识别 2&#xf…
阅读更多...
YOLOv5/v7 添加注意力机制，30多种模块分析③，GCN模块，DAN模块

YOLOv5/v7 添加注意力机制，30多种模块分析③，GCN模块，DAN模块

目录 一、注意力机制介绍1、什么是注意力机制&#xff1f;2、注意力机制的分类3、注意力机制的核心 二、GCN 模块1、GCN 模块的原理2、实验结果3、应用示例 三、DAN模块1、DAN模块的原理2、实验结果3、应用示例 大家好&#xff0c;我是哪吒。 &#x1f3c6;本文收录于&#xf…
阅读更多...
AMC12和高考数学哪个更难？知识点有哪些不同？

AMC12和高考数学哪个更难？知识点有哪些不同？

AMC12和高考数学哪个更难&#xff1f;知识点有哪些不同&#xff1f;今天小编给大家来详细介绍一下&#xff01; 难度对比 从难度上看&#xff0c;高考数学的计算量更大&#xff0c;并且知识点比AMC10/12超前&#xff0c;需要用到极限和微积分的知识。 反观AMC10/12不需要用到…
阅读更多...
数据结构与算法之美 | 栈

数据结构与算法之美 | 栈

栈结构&#xff1a;后进者先出&#xff0c;先进者后出 栈是一种“操作受限”的线性表 当某个数据集合只涉及在一端插入和删除数据&#xff0c;并且满足后进先出、先进后出的特性&#xff0c;这时我们就应该首选“栈”这种数据结构 栈的实现 使用数组实现&#xff1a;顺序栈…
阅读更多...
初探图神经网络——GNN

初探图神经网络——GNN

title: 图神经网络(GNN) date: tags: 随笔知识点 categories:[学习笔记] 初探图神经网络(GNN) 文章来源&#xff1a;https://distill.pub/2021/gnn-intro/ 前言&#xff1a;说一下为什么要写这篇文章&#xff0c;因为自己最近一直听说“图神经网络”&#xff0c;但是一直不了…
阅读更多...
pycharm使用之torch_sparse安装

pycharm使用之torch_sparse安装

正式安装之前要先查看一下torch的版本 一、查看torch版本 1、winR &#xff0c;输入cmd 2、输入python 3、 输入import torch&#xff0c;然后输入torch.__version__&#xff0c;最后回车 可以看到我的torch版本是1.10.0 二、下载合适的torch_sparse版本 1、打开链接 https…
阅读更多...
接口反应慢优化

接口反应慢优化

遇到某个功能&#xff0c;页面转圈好久&#xff0c;需要优化 1.F12 查看接口时间 2.看参数 总共耗时9.6s Waiting for sercer response 时间是2秒 Content Download 7秒 慢在Content Download F12查看接口响应 显示Failed to load response data:Request content was e…
阅读更多...
spark入门 高可用部署HA（五)

spark入门 高可用部署HA（五)

一、standalone基于修改部署 https://blog.csdn.net/weixin_43205308/article/details/131070277?spm1001.2014.3001.5501 二、安装ZOOKEEPER zookeeper 安装下载与集群 三、修改conf下的spark-env.sh vim conf/spark-env.sh注释以下内容&#xff08;根据自己环境修改&am…
阅读更多...
visual studio 2022，ADO.NET 实体数据模型添加 sqlite数据库对象

visual studio 2022，ADO.NET 实体数据模型添加 sqlite数据库对象

文章目录 前言前期环境博客github 文档解析文件安装说明文件下载省流版nuget环境配置成功标志sqlite连接测试 前言 我们知道ADO.NET 实体数据模型特别适合动态开发数据库。因为ADO.NET可以使用DB First 开发 我们在开发一个程序的时候&#xff0c;经常会动态更新数据库字段&a…
阅读更多...
算法模板（3）：搜索（4）：高等图论

算法模板（3）：搜索（4）：高等图论

高等图论 有向图的强连通分量 相关概念 强连通分量&#xff1a;Strongly Connected Component (SCC).对于一个有向图顶点的子集 S S S&#xff0c;如果在 S S S 内任取两个顶点 u u u 和 v v v&#xff0c;都能找到一条 u u u 到 v v v 的路径&#xff0c;那么称 S S…
阅读更多...
C++多态和文件读写

C++多态和文件读写

C黑马&#xff0c;每天1.5倍速2个视频&#xff08;1小时&#xff09;&#xff0c;看到9月1日完成314个视频 目录 &#x1f511;多态 &#x1f333;基本语法 &#x1f333;原理剖析 &#x1f333;案例1 -- 计算器类 &#x1f333;纯虚函数和抽象类 &#x1f333;案例2 --…
阅读更多...
最新文章

Copyright @ 2022~2023