首页 > 其他分享 >DP：01背包问题

DP：01背包问题

时间：2024-06-23 00:01:00浏览次数：8  
标签：vector 01 nums int aim 背包 DP dp

一、背包问题的概述

背包问题是⼀种组合优化的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];
    }
};

 

标签：vector,01,nums,int,aim,背包,DP,dp
From： https://blog.csdn.net/weixin_51142926/article/details/139484255

相关文章

  • 代码随想录第13天 | 二叉树part01 基础和遍历
    二叉树基础知识二叉树种类满二叉树满二叉树：如果一棵二叉树只有度为0和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树（子节点要么为0，要么为2）若满二叉树的深度为k（即k层，从1开始），则其节点个数为：2^k-1完全二叉树完全二叉树：从上到下，从左到右，都是连续的。满二叉树一......
  • P1971 [NOI2011] 兔兔与蛋蛋游戏 题解
    Description这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。这个游戏是在一个\(n\)行\(m\)列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：兔兔每次操作......
  • 一步一步拿下WordPress网站
    信息收集——主机发现主机发现也采用arp-scan、netdiscover、fping等工具信息收集——端口扫描使用nmap对发现的主机IP进行扫描命令：nmap-sS-sV-p--v-T4靶机IP信息收集——威胁建模靶机开放端口及对应的服务：22SSH服务80HTTP服务3306MySQL服务目录......
  • 【办公类-50-01】20240620自主游戏观察记录表19周内容打乱
    背景需求：又到了期末，各种班级资料需要提交。有一份自主游戏观察记录需要写19周（每周2次）的观察记录，并根据参考书填写一级、三级、五级的评价指标。去年中六班的时候，我很认真的手写了21周的户外游戏活动内容，主动成为2个需要提交文本资料的班级。今年组长选了中二和中五提交......
  • HDU-4281 Judges' response（2012 ACM/ICPC Asia Regional Tianjin Online）
    HDU-4281Judges'response（2012ACM/ICPCAsiaRegionalTianjinOnline）状态压缩+01背包+区间dp题意：有n个地点，第一个地点是裁判位置，其他n-1个地点是选手的位置。裁判要给选手解决问题，每个选手都有一个时间表示解决这个选手问题所需要的时间。同样的，裁判也有一个时间，表示这......
  • Diffusion Model-DDPM
      扩散过程是一个逐渐在数据上加噪的马尔科夫链，直到最终变成一个完全的噪声。而扩散模型就是一个使用变分推断训练的参数化马尔科夫链。如上图所示。学习的是一个reverseprocess。 前提条件：1.马尔可夫性质：当前的状态只与之前一个时刻的状态有关；2.前向和反向状态服从高......
  • Qt版本选择01
    嵌入式推荐用Qt4.8，打包的程序小：Qt4.8.7是Qt4的终结版本，是Qt4系列版本中最稳定最经典的最后支持xp系统的长期支持版本：Qt5.6.3；Qt5.7.0是最后支持xp系统的非长期支持版本。最后提供mysql数据库插件的版本：Qt5.12.3。最后支持win7的版本：Qt5.15系列。Qt6不支持win7最后样式表性能最......
  • 【B站黑马程序员LINUX 学习笔记 01】
    课程看的是b站黑马程序员的https://www.bilibili.com/video/BV1n84y1i7td/?spm_id_from=333.337.search-card.all.click&vd_source=be621a30ea2e4e0374f5df95b0b017f201操作系统概述计算机由：硬件和软件组成。操作系统是计算机软件的一种，它主要负责:作为用户和计算机硬件......
  • GridPane网格布局
    JavaFX的GridPane是一种基于网格的布局方式，它允许你将子节点放置在网格的行和列中。GridPane提供了高度的灵活性来创建复杂的用户界面布局。以下是GridPane的一些基本用法：添加节点到网格：使用add方法将子节点添加到特定的行和列。行和列的索引：行和列的索引都是从0开......
  • 电压互感器（zmpt101b）交流电压采样
        交流电压采样是我们在控制逆变电路时重要的一环。有一种采样方法就是用电压互感器+运放将目标交流电压转化为单片机可以测量的电压（即控制在合适的大小内，并且均转化为正值）。    在淘宝上我们可以买到现成的互感器模块，如下图： 其原理图如下：感谢@qq_389......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99