1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：川入 分类：Toy博客 阅读(56) 违法举报

这篇具有很好参考价值的文章主要介绍了【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

背包问题概述

01 背包问题

01背包⭐⭐ 

【算法原理】

第一问

第二问

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

分割等和子集⭐⭐

【算法原理】 

对于类01背包问题

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

目标和⭐⭐

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

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

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

背包问题概述

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

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

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

01 背包问题

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

01背包⭐⭐ 

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

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

【算法原理】

第一问

#：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 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 ])。

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

#：初始化：

       我们多加⼀行，方便我们的初始化，此时仅需将第⼀行初始化为 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 的情况。

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

#：填表顺序：

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

#：返回值：

        由于最后可能凑不成体积为 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 ])，可以发现只是和两行有关，所以我们就可以首先用两个一维数组解决。

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

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

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

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

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;
}

优化细节：

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

        因为如果出现 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背包问题,动态规划专栏,动态规划,算法,c++,01背包

​

【算法原理】 

对于类01背包问题

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

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

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

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,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）

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

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

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,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 ]]。

         综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移方程为：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。

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

#：填表顺序：

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

#：返回值：

        根据「状态表示」，返回 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）

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

【算法原理】 

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

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

动态规划01背包问题,动态规划专栏,动态规划,算法,c++,01背包

  • 又因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越小。
        因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近 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背包问题一样。文章来源地址https://www.toymoban.com/news/detail-744525.html

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];
    }
};

到了这里，关于【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】01背包问题——算法设计与分析

    【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包，选择一件或多件商品带走，则如何选择可以使得收益最高？ 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入： quad - n n n 个商品组成集合 O O O ，每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(79)
  • 【Java实现】动态规划算法解决01背包问题

    【Java实现】动态规划算法解决01背包问题

    1、问题描述： 一个旅行者有一个最多能装m公斤的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？ 2、动态规划算法的概述 1）动态规划(Dynamic Progra

    2023年04月09日
    浏览(56)
  • 算法分析与设计——动态规划求解01背包问题

    算法分析与设计——动态规划求解01背包问题

    假设有四个物品，如下图，背包总容量为8，求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题，首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如， (4, 8)表示在背包容量为8的情况下，前四个物品的最

    2024年02月04日
    浏览(70)
  • 【动态规划】背包问题题型及方法归纳

    【动态规划】背包问题题型及方法归纳

    背包问题是在规定背包容量为j的前提下，每个物品对应的体积为v[i]，价值为w[i]，从物品0到物品i中选择物品放入背包中， 找出符合某种要求的价值 。 （1）背包问题种类 01背包：每种物品只能选择1个。 完全背包：每种物品可以选择无限个。 多重背包：每种物品最多可选

    2024年02月02日
    浏览(42)
  • 算法套路十四——动态规划之背包问题：01背包、完全背包及各种变形

    算法套路十四——动态规划之背包问题：01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解，可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍：https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品，第i个物品的体积为w[i]，价值为v[i]，每个物品至多选一个， 求体积和不超过capacity时的最大价值和，其中i从

    2024年02月10日
    浏览(59)
  • C++算法初级11——01背包问题（动态规划2）

    C++算法初级11——01背包问题（动态规划2）

    辰辰采药 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时

    2024年02月02日
    浏览(50)
  • 【算法日志】动态规划刷题：01背包问题，多重背包问题(day37,day38)

    【算法日志】动态规划刷题：01背包问题，多重背包问题(day37,day38)

    目录 前言 目标和（01背包） 一和零（01背包） 零钱兑换（多重背包） 排列总和（多重背包） 这两天都是背包问题，其中的01背包的一些应用问题需要一定的数学建模能力，需要i将实际问题简化成我们熟悉的背包问题；而这两天的多重背包问题还算比较基础，但也要我明白了

    2024年02月11日
    浏览(56)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页：兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(50)
  • 算法设计与分析实验二：动态规划法求解TSP问题和01背包问题

    算法设计与分析实验二：动态规划法求解TSP问题和01背包问题

    【实验内容】 （1）tsp问题：利用动态规划算法编程求解TSP问题，并进行时间复杂性分析。 输入：n个城市,权值，任选一个城市出发； 输出：以表格形式输出结果，并给出向量解和最短路径长度。 （2）01背包问题：利用动态规划算法编程求解0-1背包问题，并进行时间复杂性分

    2024年02月03日
    浏览(58)

  • 力扣算法刷题Day42｜动态规划：01背包问题 分割等和子集

    力扣题目：01背包问题（二维数组） 刷题时长：参考题解 解题方法：动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路：两层for循环，第一层i遍历物品，第二层j枚举背包容量以内所有值 确定dp数组及下标的含义：dp[i][j] 表示从下标

    2024年02月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包