DP：01背包问题

一、背包问题的概述

背包问题是⼀种组合优化的NP完全问题。
本质上是为了找出“带有限制条件的组合最优解”

1、根据物品的个数，分为如下几类：

• 01背包问题：每个物品只有⼀个（重点掌握）
• 完全背包问题：每个物品有无限多个（重点掌握）
• 多重背包问题：每件物品最多有n个
• 混合背包问题：每个物品会有上⾯三种情况
• 分组背包问题：物品有n组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品

2、根据背包是否装满，⼜分为两类

• 不⼀定装满背包（重点）
• 背包⼀定装满（重点）

3、优化方案

• 空间优化：滚动数组（重点掌握）
• 单调队列优化
• 贪心优化

4、根据限定条件的个数，⼜分为两类

• 限定条件只有⼀个：比如体积->普通的背包问题（重点）
• 限定条件有两个：比如体积+重量->⼆维费用背包问题（重点）

5、根据不同的问法，⼜分为很多类：

• 输出方案
• 求方案总数
• 最优方案
• 方案可行性

        背包问题的题型非常多样，其中最重要以及基础的就是01背包和完全背包以及背包是否装满的讨论（会通过牛客的两道模版题探究），还有滚动数组的优化策略（ 在以往的动态规划中，我们几乎很少去谈论空间优化，因为对于一道dp题来说，能解决出来就已经很不容易了，我们不太会关注其空间复杂度。但是在背包问题中，滚动数组的优化是有一定套路可言的，并且在某些情况下对时间也是有一定优化的！！）

二、01背包[模版]

【模板】01背包_牛客题霸_牛客网

#include<iostream>
#include<string.h>
using namespace std;
//定义成全局，就不用在栈里面进行初始化，并且我们可以在栈上开辟的空间更大

const int N=1001;
int n,V,v[N],w[N];
int dp[N][N];

int main() 
{
   cin>>n>>V;//个数和体积
   for(int i=1;i<=n;++i) cin>>v[i]>>w[i];

   //解决第一问
   for(int i=1;i<=n;++i)
     for(int j=1;j<=V;++j)
      {
        dp[i][j]=dp[i-1][j];//不选第i个物品的情况
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
      }   
      cout<<dp[n][V]<<endl;
    //解决第二问
    memset(dp,0,sizeof dp);//修改成0
    //先进行初始化
    for(int j=1;j<=V;++j) dp[0][j]=-1;//跟0区分开
     for(int i=1;i<=n;++i)
     for(int j=1;j<=V;++j)
      {
        dp[i][j]=dp[i-1][j];//不选第i个物品的情况
        if(j>=v[i]&&dp[i-1][j-v[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
      }   
      cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
}

滚动数组优化（空间复杂度N^2——>N   时间复杂度常数提升）

#include<iostream>
#include<string.h>
using namespace std;
//定义成全局，就不用在栈里面进行初始化，并且我们可以在栈上开辟的空间更大
const int N=1001;
int n,V,v[N],w[N];
int dp[N][N];

int main() 
{
   cin>>n>>V;//个数和体积
   for(int i=1;i<=n;++i) cin>>v[i]>>w[i];

   //解决第一问
   for(int i=1;i<=n;++i)
     for(int j=V;j>=v[i];--j)
       dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      cout<<dp[V]<<endl;
    //解决第二问
    memset(dp,0,sizeof dp);//修改成0
    //先进行初始化
    for(int j=1;j<=V;++j) dp[j]=-0x3f3f3f3f;//跟0区分开
     for(int i=1;i<=n;++i)
     for(int j=V;j>=v[i];--j)
         dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      cout<<(dp[V]<0?0:dp[V])<<endl;
}

       对于不存在的状态，因为我们该题中要求的是max，所以我们设成-0x3f3f3f3f保证该状态不被选到，设置成这个的原因是避免了越界的风险同时又保证了不存在的状态是小于0的，且不会影响填报！！

三、和为目标和的最长子序列长度

. - 力扣（LeetCode）

       这题就是非常明显的01背包问题，其中每个数只有选或者不选，目标值相当于是容量，且要刚刚好。 dp[i][j]表示从前i个数选，和恰好为j的最长子序列。

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n=nums.size();
        //01背包问题  dp[i][j]表示从前i个数选择 正好凑成j的的子序列的最长长度
        vector<vector<int>> dp(n+1,vector<int>(target+1));
        //分析状态转移方程 dp[i][j] 
        //如果我不选i dp[i-1][j]
        //如果我选i   dp[i-1][j-nums[i-1]]+1 
        //初始化 如果i为0无数可选  没有这个状态
        for(int j=1;j<=target;++j) dp[0][j]=-0x3f3f3f3f;//给一个小的值  保证选最大值的时不会被选上
        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]=max(dp[i][j],dp[i-1][j-nums[i-1]]+1);
            }
            return dp[n][target]<0?-1:dp[n][target];
    }
};

滚动数组优化：

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n=nums.size();
        //01背包问题  dp[i][j]表示从前i个数选择 正好凑成j的的子序列的最长长度
        vector<int> dp(target+1,-0x3f3f3f3f);
        //分析状态转移方程 dp[i][j] 
        //如果我不选i dp[i-1][j]
        //如果我选i   dp[i-1][j-nums[i-1]]+1 
        //初始化 如果i为0无数可选  没有这个状态
        dp[0]=0;
        for(int i=1;i<=n;++i)
          for(int j=target;j>=nums[i-1];--j)
             dp[j]=max(dp[j],dp[j-nums[i-1]]+1);
            return dp[target]<0?-1:dp[target];
    }
};

四、分割等和子集（需转化）

. - 力扣（LeetCode）

该题并不能直接用01背包问题，首先需要先将问题进行转化——在数组中选一些数，让这些数的和为sum/2。 

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2) return false;//是奇数，直接返回
        //是偶数的时候 dp[i][j]表示从前i个数中选，所有选法中能否凑成j这个数
        int aim=sum/2;
        int n=nums.size();
        vector<vector<bool>> dp(n+1,vector<bool>(aim+1));
        //初始化，当j=0时，显然都是true  当i=0时，必然为false
        for(int i=0;i<=n;++i) dp[i][0]=true;
        //开始填表
        for(int i=1;i<=n;++i)
          for(int j=1;j<=aim;++j)
        //不选i的话  dp[i][j]=dp[i-1][j]
        //选i的话    dp[i][j]=dp[i-1][j-nums[i-1]]   前提j>=nums[i-1]
        {
            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]];
        }
        return dp[n][aim];
    }
};

滚动数组优化：

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2) return false;//是奇数，直接返回
        //是偶数的时候 dp[i][j]表示从前i个数中选，所有选法中能否凑成j这个数
        int aim=sum/2;
        int n=nums.size();
        vector<bool> dp(aim+1);
        //初始化，当j=0时，显然都是true  当i=0时，必然为false
        dp[0]=true;
        //开始填表
        for(int i=1;i<=n;++i)
          for(int j=aim;j>=nums[i-1];--j)
        //不选i的话  dp[i][j]=dp[i-1][j]
        //选i的话    dp[i][j]=dp[i-1][j-nums[i-1]]   前提j>=nums[i-1]
        dp[j]=dp[j]||dp[j-nums[i-1]];
        return dp[aim];
    }
};

 五、目标和（需转化）

. - 力扣（LeetCode）

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       // 从nums中选择一些数能够凑成sum+target/2  转化成01背包问题
       int sum=accumulate(nums.begin(),nums.end(),0);
       int aim=(sum+target)>>1;
       if(aim<0||(sum+target)%2) return 0;
       int n=nums.size();
       //dp[i][j] 从前i个数选 变成j有多少种选法    
        //如果不选i dp[i-1][j]
        //如果选i   +=dp[i-1][j-nums[i-1]]
        //分析初始化 i=0的时候 必为0  j=0的时候 不好判断，因为nums[i]可能是0 
        //但是不需要初始化，因为要满足j>=nums[i] 那么nums[i]必然要为0才可以满足
        //所以绝对不会用到斜对角的值，而是只会用到上面的状态。
        vector<vector<int>> dp(n+1,vector<int>(aim+1));
        dp[0][0]=1;
       for(int i=1;i<=n;++i)
        for(int j=0;j<=aim;++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][aim];
    }
};

 滚动数组优化：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       // 从nums中选择一些数能够凑成sum+target/2  转化成01背包问题
       int sum=accumulate(nums.begin(),nums.end(),0);
       int aim=(sum+target)>>1;
       if(aim<0||(sum+target)%2) return 0;
       int n=nums.size();
       //dp[i][j] 从前i个数选 变成j有多少种选法    
        //如果不选i dp[i-1][j]
        //如果选i   +=dp[i-1][j-nums[i-1]]
        //分析初始化 i=0的时候 必为0  j=0的时候 不好判断，因为nums[i]可能是0 
        //但是不需要初始化，因为要满足j>=nums[i] 那么nums[i]必然要为0才可以满足
        //所以绝对不会用到斜对角的值，而是只会用到上面的状态。
        vector<int> dp(aim+1);
        dp[0]=1;
       for(int i=1;i<=n;++i)
        for(int j=aim;j>=nums[i-1];--j) 
            dp[j]+=dp[j-nums[i-1]];
        return dp[aim];
    }
};

六、最后一块石头的重量||(需转化)

. - 力扣（LeetCode）

class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) {
      //让一堆里面的数尽可能接近sum/2
      int sum=accumulate(nums.begin(),nums.end(),0);
      int aim=sum/2,n=nums.size();
      //dp[i][j]表示从前i个数选择，总和不超过j，此时所有元素的最大和
      vector<vector<int>> dp(n+1,vector<int>(aim+1));
      //分析初始化 如果都为0 就返回0 如果i为0 也是0  如果j为0 不用初始化
      for(int i=1;i<=n;++i)
        for(int j=1;j<=aim;++j)
          {
            //如果不选i dp[i-1][j]
            //如果选i  dp[i-1][j-nums[i-1]] 找最大和
            dp[i][j]=dp[i-1][j];
            if(j>=nums[i-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
          }
        return sum-2*dp[n][aim];
    }
};

滚动数组优化：

class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) {
      //让一堆里面的数尽可能接近sum/2
      int sum=accumulate(nums.begin(),nums.end(),0);
      int aim=sum/2,n=nums.size();
      //dp[i][j]表示从前i个数选择，总和不超过j，此时所有元素的最大和
      vector<int> dp(aim+1);
      //分析初始化 如果都为0 就返回0 如果i为0 也是0  如果j为0 不用初始化
        //如果不选i dp[i-1][j]
         //如果选i  dp[i-1][j-nums[i-1]] 找最大和
      for(int i=1;i<=n;++i)
        for(int j=aim;j>=nums[i-1];--j)
           dp[j]=max(dp[j],dp[j-nums[i-1]]+nums[i-1]);
        return sum-2*dp[aim];
    }
};

七、将一个数字表示成幂的和的方案数

. - 力扣（LeetCode）

知识点1：double不支持取模，需要取模又担心溢出只能使用long long

知识点2：pow函数是求数的任意次幂

知识点3:10^9+7相当于1e9+7

class Solution {
public:
    int numberOfWays(int n, int x) {
        //统计方案数
        //dp[i][j]表示从前i个数的x次幂之和  恰好等于j 的方案数
        //i=0时 无数可选 方案肯定是
        const int N=1e9+7;
        vector<vector<long long>> dp(n+1,vector<long long>(n+1)); //double不支持取模    
        dp[0][0]=1;
        for(int i=1;i<=n;++i)
          for(int j=0;j<=n;++j)
           {
            //不选i dp[i][j]=dp[i-1][j]
            //选i   dp[i][j]+=dp[i-1][j-pow(i,x)]
             dp[i][j]=dp[i-1][j];
             long long p=pow(i,x); 
             if(j>=p) dp[i][j]+=dp[i-1][j-p];
             dp[i][j]%=N;
           }
           return dp[n][n];
    }
};

 滚动数组优化：

class Solution {
public:
    int numberOfWays(int n, int x) {
        //统计方案数
        //dp[i][j]表示从前i个数的x次幂之和  恰好等于j 的方案数
        //i=0时 无数可选 方案肯定是
        const int N=1e9+7;
        vector<long long> dp(n+1); //double不支持取模    
        dp[0]=1;
        for(int i=1;i<=n;++i)
        {
            long long p=pow(i,x);
          for(int j=n;j>=p;--j)
            //不选i dp[i][j]=dp[i-1][j]
            //选i   dp[i][j]+=dp[i-1][j-pow(i,x)]
             dp[j]=(dp[j]+dp[j-p])%N;
        }
           return dp[n];
    }
};

 

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

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

相关文章

【如何保持专注】

【如何保持专注】

今日&#x1f4d2;&#xff0c;看博主分享下保持专注的新方法&#xff0c;有点意思 &#xff0c; 怎么保持专注&#xff0c;给大家分享两个极客的方法啊。 第一个呢是来自于一个非常著名的程序员啊&#xff0c;叫做这个尼克温特&#xff0c;大家有兴趣可以查一下&#xff0c;就…
阅读更多...
探究肥胖致血糖异常的原因与运动的意义

探究肥胖致血糖异常的原因与运动的意义

肥胖对身体血糖存在影响&#xff0c;原因主要在于以下两方面。 首先&#xff0c;肥胖者体内的脂肪组织大量积聚&#xff0c;会释放诸多有害物&#xff0c;对胰岛素的正常功能形成干扰&#xff0c;致使胰岛素抵抗加剧&#xff0c;从而造成血糖调节失常。 其次&#xff0c;肥胖往…
阅读更多...
Spring AI探索

Spring AI探索

Spring AI概述 该Spring AI项目旨在简化包含人工智能功能的应用程序的开发&#xff0c;避免不必要的复杂性。 该项目从著名的 Python 项目&#xff08;例如 LangChain 和 LlamaIndex&#xff09;中汲取灵感&#xff0c;但 Spring AI 并非这些项目的直接移植。该项目的成立基于…
阅读更多...
Day 24：100301. 构成整天的下标对数目II

Day 24：100301. 构成整天的下标对数目II

Leetcode 100301. 构成整天的下标对数目II 给你一个整数数组 hours&#xff0c;表示以 **小时 **为单位的时间&#xff0c;返回一个整数&#xff0c;表示满足 i < j 且 hours[i] hours[j] 构成 **整天 **的下标对 i, j 的数目。 **整天 **定义为时间持续时间是 24 小时的 *…
阅读更多...
Electron+vite+vuetify项目搭建

Electron+vite+vuetify项目搭建

最近想用Electron来进行跨平台的桌面应用开发。同时想用vuetify作为组件&#xff0c;于是想搭建一个这样的开发环境。其中踩了不少坑&#xff0c;总是会出现各种的编译错误和问题&#xff0c;依赖的各种问题&#xff0c;搞了好久最终环境终于弄好可正常开发了。这里分享下快速搭…
阅读更多...
C语言王国——深入自定义类型（结构体）

C语言王国——深入自定义类型（结构体）

目录 一、引言 二、结构体 1. 结构体类型的声明 2. 结构体变量的创建和初始化 2.1 创建 2.2 初始化 2.3 typedef 2.4 特殊声明 2.5 自引用 3. 结构成员访问操作符 4. 结构体内存对齐 4.1 对齐规则 4.2 offsetof 4.3 为什么存在内存对齐 5. 结构体传参 6. 结构体实现…
阅读更多...
力扣191. 位1的个数

力扣191. 位1的个数

Problem: 191. 位1的个数 文章目录 题目描述思路复杂度Code 题目描述 思路 题目规定数值的范围不会超过32位整形数 1.定义统计个数的变量oneCount&#xff1b;由于每次与给定数字求与的变量mask初始化为1 2.for循环从0~32&#xff0c;每一次拿mask与给定数字求与运算&#xff…
阅读更多...
单向散列函数解析

单向散列函数解析

目录 1. 概述 2. 单向散列函数的性质 2.1 根据任意长度的消息计算出固定长度的散列值 2.2 能够快速计算出散列值 2.3 消息不同散列值也不同 2.4 具备单向性 3. 单向散列函数的算法 3.1 MD5 3.2 SHA序列 3.3 SM3 1. 概述 针对计算机所处理的消息&#xff0c;有时候我们…
阅读更多...
GitLab、jenkins

GitLab、jenkins

Gitlab服务器&#xff1a;192.168.10.20 jenkins服务器&#xff1a;192.168.10.30 web应用服务器&#xff1a;192.168.10.100 通过容器部署gitlab&#xff1a; 安装容器管理软件podman 修改主机的22端口&#xff0c;该gitlab软件包中会使用到该端口 gitlab容器需要使用/etc/res…
阅读更多...
Thinkphp起名网宝宝起名网站源码

Thinkphp起名网宝宝起名网站源码

Thinkphp起名网宝宝起名网站源码 源码介绍 1.宝宝在线起名 2.八字起名&#xff0c;周易取名 3.一对一起名 5.支持手机wap 链接数据库地址&#xff1a;Application\Common\Conf 修改里面config.php数据库连接&#xff0c;导入sm.sql数据库文件即可 伪静态用thinkphp 后台…
阅读更多...
Centos部署openGauss6.0创新版本，丝滑的体验

Centos部署openGauss6.0创新版本，丝滑的体验

作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验&#xff0c; Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯及Greenplum备份恢复&#xff0c; 安装迁移&#xff0c;性能优化、故障…
阅读更多...
主流框架选择：React、Angular、Vue的详细比较

主流框架选择：React、Angular、Vue的详细比较

目前前端小伙伴经常使用三种广泛使用的开发框架&#xff1a;React、Angular、Vue - 来设计网站 Reactjs&#xff1a;效率和多功能性而闻名 Angularjs&#xff1a;创建复杂的应用程序提供了完整的解决方案&#xff0c;紧凑且易于使用的框架 Vuejs&#xff1a;注重灵活性和可重用…
阅读更多...
Java | Leetcode Java题解之第155题最小栈

Java | Leetcode Java题解之第155题最小栈

题目&#xff1a; 题解&#xff1a; class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack new LinkedList<Integer>();minStack new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void …
阅读更多...
【ComfyUI】图像重绘/ 图像到图像生成——Comfyui的基本使用（三）

【ComfyUI】图像重绘/ 图像到图像生成——Comfyui的基本使用（三）

参考&#xff1a;ComfyUI的安装与使用&#xff08;一&#xff09;&#xff08;windows1660ti 6G显存&#xff09; 草稿img2img 工作流展示&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1Nv68-e4glh6lD7N9KB_-Pg?pwd0614 a tiger with anger emotion ,best qualit…
阅读更多...
每日一题——冒泡排序

每日一题——冒泡排序

C语言——冒泡排序 冒泡排序练习 前言&#xff1a;CSDN的小伙伴们&#xff0c;大家好&#xff01;今天我来给大家分享一种解题思想——冒泡排序。 冒泡排序 冒泡法的核心思想&#xff1a;两两相邻的元素进行比较 2.冒泡排序的算法描述如下。 (1)比较相邻的元素。如果第一 个比…
阅读更多...
图书馆图书可视化分析+大屏

图书馆图书可视化分析+大屏

&#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能&#xff01; &#x1f31f;博客的简介&#xff08;文章目录&#xff09; 目录 摘要前言技术栈开发环境数据说明 正文数据获取数据存储数据清理数据分析数据挖掘关联规则二分类预测 数据可视化书籍价格区间柱状图书籍评…
阅读更多...
MySQL面试重点-1

MySQL面试重点-1

1. 数据库基础知识&#xff1a; DDL、DML、DQL、DCL的概念与区别&#xff1f; DDL&#xff08;数据定义语言&#xff09;&#xff1a;创建&#xff08;CREATE&#xff09;数据库中的各种对象&#xff1a;表、视图、索引等DML&#xff08;数据操纵语言&#xff09;&#xff1a…
阅读更多...
教学资源共享平台的设计

教学资源共享平台的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;老师管理&#xff0c;用户管理&#xff0c;成绩管理&#xff0c;教学资源管理&#xff0c;作业管理 老师账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用…
阅读更多...
基于SSM+Jsp的旅游景点线路网站

基于SSM+Jsp的旅游景点线路网站

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…
阅读更多...
【QT5】＜总结＞ QT主要技术点

【QT5】＜总结＞ QT主要技术点

文章目录 前言 一、QT串口编程 二、QT网络编程 三、QT多线程 四、开发板上运行QT程序 前言 在学习QT的过程中&#xff0c;旨在更好地巩固所学到的知识&#xff0c;本篇总结QT在嵌入式开发中的主要技术点。 一、QT串口编程 思维导图&#xff1a; 知识点&#xff1a;【QT5…
阅读更多...
最新文章

Copyright @ 2022~2023