DP:完全背包+多重背包问题

完全背包和01背包的区别就是:可以多次选

一、完全背包(模版)

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

#include <iostream>
#include<string.h>
using namespace std;
const int N=1001;
int n,V,w[N],v[N],dp[N][N];
//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-2v[i]]+2w[i]……)
//数学dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i]……)
//dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]])
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];
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }  
      cout<<dp[n][V]<<endl;
    //解决第二问 //dp[i][j]表示从前i个物品选,体积正好为j的最大价值
     memset(dp,0,sizeof dp);
     //约定-1表示状态选不到 当i=0时 j>=1时  必然是没有状态的
     for(int j=1;j<=V;++j) dp[0][j]=-1;
      for(int i=1;i<=n;++i)
    for(int j=1;j<=V;++j)
      {
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]&&dp[i][j-v[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }  
      cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
        return 0;
}

滚动数组的优化策略:

 区分:01背包的优化得是从右往左,而完全背包的优化得是从左往右

#include <iostream>
#include<string.h>
using namespace std;
const int N=1001;
int n,V,w[N],v[N],dp[N];
//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-2v[i]]+2w[i]……)
//数学dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i]……)
//dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]])
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[i];j<=V;++j)
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      cout<<dp[V]<<endl;
    //解决第二问 //dp[i][j]表示从前i个物品选,体积正好为j的最大价值
     memset(dp,0,sizeof dp);
     //约定-1表示状态选不到 当i=0时 j>=1时  必然是没有状态的
     for(int j=1;j<=V;++j) dp[j]=-0x3f3f3f3f;
      for(int i=1;i<=n;++i)
    for(int j=v[i];j<=V;++j)
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      cout<<(dp[V]<0?0:dp[V])<<endl;
     return 0;
}

 二、零钱兑换

. - 力扣(LeetCode)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数
        //如果不选i dp[i-1][j]
        //选1个i   dp[i-1][j-coins[i-1]]+1
        //dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i-1]]+1,dp[i-1][j-2coins[i-1]]+2……)
        //dp[i][j-coins[i-1]]=min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]+1……)
        //dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)
        const int INF=0x3f3f3f3f;
        int n=coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1));
        for(int j=1;j<=amount;++j) dp[0][j]=INF;
        for(int i=1;i<=n;++i)
          for(int j=1;j<=amount;++j)
           {
            dp[i][j]=dp[i-1][j];
            if(j>=coins[i-1])  dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
           }
         return dp[n][amount]>=INF?-1:dp[n][amount];
    }
};

 滚动数组优化:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数
        //如果不选i dp[i-1][j]
        //选1个i   dp[i-1][j-coins[i-1]]+1
        //dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i-1]]+1,dp[i-1][j-2coins[i-1]]+2……)
        //dp[i][j-coins[i-1]]=min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]+1……)
        //dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)
        const int INF=0x3f3f3f3f;
        int n=coins.size();
        vector<int> dp(amount+1,INF);
        dp[0]=0;
        for(int i=1;i<=n;++i)
          for(int j=coins[i-1];j<=amount;++j)
            dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
         return dp[amount]>=INF?-1:dp[amount];
    }
};

三、零钱兑换II

. - 力扣(LeetCode)

class Solution {
public:
    int change(int amount, vector<int>& coins) {
       //dp[i][j]表示从前i个硬币选,正好可以凑成总金额的硬币组合数
       //如果i不选 dp[i][j]+=dp[i-1][j]
       //如果i选1个 dp[i][j]+=dp[i-1][j-coins[i-1]]
       //dp[i][j]+=dp[i-1][j-coins[i-1]]+=dp[i-1][j-2coins[i-1]]……
       //dp[i][j]+=dp[i][j-coins[i-1]]
       int n=coins.size();
       //分析初始化 当j=0 都是一种选法  当i=0时 无论如何凑不出j 状态无效
       vector<vector<int>> dp(n+1,vector<int>(amount+1));
       dp[0][0]=1;
       for(int i=1;i<=n;++i)
         for(int j=0;j<=amount;++j) //不会越界,可以从0开始
         {
           dp[i][j]+=dp[i-1][j];
           if(j>=coins[i-1]) dp[i][j]+=dp[i][j-coins[i-1]];
         }
       return dp[n][amount];
    }
};

滚动数组做优化:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
       //dp[i][j]表示从前i个硬币选,正好可以凑成总金额的硬币组合数
       //如果i不选 dp[i][j]+=dp[i-1][j]
       //如果i选1个 dp[i][j]+=dp[i-1][j-coins[i-1]]
       //dp[i][j]+=dp[i-1][j-coins[i-1]]+=dp[i-1][j-2coins[i-1]]……
       //dp[i][j]+=dp[i][j-coins[i-1]]
       int n=coins.size();
       //分析初始化 当j=0 都是一种选法  当i=0时 无论如何凑不出j 状态无效
      vector<int> dp(amount+1);
       dp[0]=1;
       for(int i=1;i<=n;++i)
         for(int j=coins[i-1];j<=amount;++j) //不会越界,可以从0开始
           dp[j]+=dp[j-coins[i-1]]; //+= 0不会影响填表
       return dp[amount];
    }
};

四、完全平方数

. - 力扣(LeetCode)

class Solution {
public:
//不能用贪心策略 比如说1 4 9   组成12    444比9111好
    int numSquares(int n) {
      //1 4 9 16 25……
      //dp[i][j]表示从前i个数选,刚好为j的最少数量
      const int INF=0x3f3f3f3f;
      int m=sqrt(n);
      vector<int> dp(n+1,INF);
      //i=0的时候 不可能凑成j  j=0时 i取1
      dp[0]=0;
    for(int i=1;i<=m;++i)
      for(int j=i*i;j<=n;++j)
         dp[j]=min(dp[j],dp[j-i*i]+1);
      return dp[n]; //一定能选得到,因为1是平方数 所以必然能凑出来
    }
};

五、数位成本和为目标值的最大数字(经典dp还原)

. - 力扣(LeetCode)

class Solution {
public:
    string largestNumber(vector<int>& nums, int t) {
      //考虑数值长度问题,每个数字有相应成本,且长度均为1 
      //有若干物品,求给定费用下所能选择的最大价值  (完全背包)
      //得到的就是最大位数 然后从后往前想办法还原回来
      vector<int> dp(t+1,-0x3f3f3f3f);//会有不存在的状态
      //dp[i][j]表示前i个数选择 正好为j的最大选择数目
      dp[0]=1;
      for(int i=1;i<=9;++i)
        for(int j=nums[i-1];j<=t;++j)
          dp[j]=max(dp[j],dp[j-nums[i-1]]+1);
          //此时 dp[t]里存的就是选择的最大位数 然后要想办法进行还原
          if(dp[t]<0) return "0";
          string ret;
          //开始还原 从后往前还原
          for(int i=9;i>=1;--i)
          {
             int u=nums[i-1];
             while(t>=u&&dp[t]==dp[t-u]+1)//说明选到这个数了
               {
                ret+=to_string(i);
                t-=u;
               }
          }
        return ret;
    }
};

六、获得分数的方法数(多重背包)

. - 力扣(LeetCode)

 该种类型题的具体分析请看第7题!!

class Solution {
public:
    const int MOD=1e9+7;
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        //dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] 
        //如果不选这个数 dp[i-1][j]
        //如果选 1个  dp[i-1][j-p[0]] 
        //如果选2个  dp[i-1][j-2p[0]]
        int n=types.size();
        vector<vector<int>> dp(n+1,vector<int>(target+1));
        //初始化当i为0时 
        dp[0][0]=1;
        for(int i=1;i<=n;++i)
        {
            int count=types[i-1][0],mark=types[i-1][1]; //count表示这道题的题数(选择次数)  mark表示这道题的分数
            for(int j=0;j<=target;++j)
            {
                dp[i][j]=dp[i-1][j];
                for(int k=1;k<=count;++k)
                {
                    if(j>=k*mark) dp[i][j]=(dp[i][j]+dp[i-1][j-k*mark])%MOD;
                }
            }
        }
        return dp[n][target];
    }
};

滚动数组优化 

class Solution {
public:
    const int MOD=1e9+7;
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        //dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] 
        //如果不选这个数 dp[i-1][j]
        //如果选 1个  dp[i-1][j-p[0]] 
        //如果选2个  dp[i-1][j-2p[0]]
        vector<int> dp(target+1);
        //初始化当i为0时 
        dp[0]=1;
        for(auto&p:types)
        {
            int count=p[0],mark=p[1]; //count表示这道题的题数(选择次数)  mark表示这道题的分数       //会用到上一层的状态,所以滚动数组应该要从后往前
            for(int j=target;j>=0;--j)
            {
                count=min(count,j/mark);
                for(int k=1;k<=count;++k)
                   dp[j]=(dp[j]+dp[j-k*mark])%MOD;
            }
        }
        return dp[target];
    }
};

进阶优化:

class Solution {
public:
    const int MOD=1e9+7;
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        //dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] 
        //如果不选这个数 dp[i-1][j]
        //如果选 1个  dp[i-1][j-p[0]] 
        //如果选2个  dp[i-1][j-2p[0]]
        //dp[i][j]+=dp[i-1][j-p[0]]……
        //dp[i][j-p[0]+=dp[i-1]][j-]
        vector<int> dp(target+1);
        //初始化当i为0时 
        dp[0]=1;
        for(auto&p:types)
        {
            int count=p[0],mark=p[1]; //count表示这道题的题数(选择次数)  mark表示这道题的分数       //会用到上一层的状态,所以滚动数组应该要从后往前
            for(int j=mark;j<=target;++j)
            dp[j]=(dp[j]+dp[j-mark])%MOD;
            for(int j=target;j>=(count+1)*mark;--j)
            dp[j] = (dp[j] - dp[j - mark*(count + 1)] + MOD) % MOD; // 两个同余前缀和的差
            //防止搞出负数
        }
        return dp[target];
    }
};

七、带和限制的子多重集合的数目(经典多重背包模版题)

. - 力扣(LeetCode)

 直接做滚动数组优化:

class Solution {
public:
      const int MOD=1e9+7;
    int countSubMultisets(vector<int>& nums, int l, int r) {
        //01背包 每个数选或者不选 限制范围是l-r
        //dp[i][j]表示从前i个数选  凑成和恰好为j
        //但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次
        unordered_map<int,int> hash;
        int total=0;
        for(auto&e:nums) 
        {
              total+=e;
              ++hash[e];
        }
        if(l>total) return 0;
        r=min(r,total);
        vector<int> dp(r+1);
        //初始化 i=0时 无数可选
        dp[0]=hash[0]+1;
        hash.erase(0);
        int t=0;
        for(auto[x,c]:hash) //x是数 c是他的限制次数
          for(int j=r;j>=x;--j)
           {
               c=min(c,j/x);
             for(int k=1;k<=c;++k)    //费时间 想办法用新的状态
                 dp[j]=(dp[j]+dp[j-k*x])%MOD; 
           }
         int sum=0;
         for(int j=l;j<=r;++j)
            sum=(sum+dp[j])%MOD;
            return sum;
    }
};

我们会发现由于数据量太大,用循环会超时,因此我们在这里不能用k那一层循环!!得换个方式

class Solution {
public:
      const int MOD=1e9+7;
    int countSubMultisets(vector<int>& nums, int l, int r) {
        //01背包 每个数选或者不选 限制范围是l-r
        //dp[i][j]表示从前i个数选  凑成和恰好为j
        //但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次
        //类比完全背包的状态 dp[]
        unordered_map<int,int> hash;
        int total=0;
        for(auto&e:nums) 
        {
              total+=e;
              ++hash[e];
        }
        if(l>total) return 0;
        r=min(r,total);
        vector<int> dp(r+1);
        dp[0]=hash[0]+1;
        hash.erase(0);
        // dp[i][j]+=  dp[i-1][j-x]+dp[i-1][j-2*x]……
        // dp[i][j-x]+=dp[i-1][j-2x]+dp[i-1][j-3x]……
        int sum=0;
        for(auto[x,c]:hash)
        {
             sum = min(sum+x*c,r);//目前为止 能选的元素和之多为sum 
            for (int j = x; j <= sum; j++)
                dp[j] = (dp[j] + dp[j - x]) % MOD; // 原地计算同余前缀和
             for (int j =sum;j >= x * (c + 1); j--)
                dp[j] = (dp[j] - dp[j - x * (c + 1)] + MOD) % MOD; // 两个同余前缀和的差
                //防止搞出负数
        }
        
         int ret=0;
         for(int j=l;j<=r;++j)
            ret=(ret+dp[j])%MOD;
            return ret;
    }
};

 

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

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

相关文章

IDEA 学习之 打开一个 MAVEN 工程

目录 1. 单体工程2. 多 module 工程3. 多个多 module 工程3.1. 重复 1 步骤3.2. 添加其他多 module 工程 1. 单体工程 2. 多 module 工程 3. 多个多 module 工程 3.1. 重复 1 步骤 3.2. 添加其他多 module 工程

适合孩子学习用什么的落地灯?五款精品护眼大路灯分享

适合孩子学习用什么的落地灯&#xff1f;说到护眼落地灯&#xff0c;都会出现两种呼声&#xff1a;一种是认为是“智商税”&#xff0c;而另外一种则是妥妥的照明神器&#xff01;护眼大路灯到底是哪种定义呢&#xff1f;贵的护眼灯一定好吗&#xff1f; 这么年&#xff0c;护…

学习新语言方法总结(一)

随着工作时间越长&#xff0c;单一语言越来越难找工作了&#xff0c;需要不停地学习新语言来适应&#xff0c;总结一下自己学习新语言的方法&#xff0c;这次以GO为例&#xff0c;原来主语言是PHP &#xff0c;自学GO 了解语言特性&#xff0c;知道他是干嘛的 go语言&#xff0…

【JavaEE进阶】Spring统一功能处理:拦截器的使用

目录 1.什么是拦截器? 2.拦截器的使用 2.1定义拦截器 2.2 注册配置拦截器 3.拦截器详解 3.1 拦截路径 3.2 拦截器的执行流程 4. 使用拦截器实现登录校验 4.1 定义拦截器 4.2 注册配置拦截器 1.什么是拦截器? 拦截器是Spring框架提供的核心功能之⼀, 主要用来拦截用…

数据分析必备:一步步教你如何用matplotlib做数据可视化(8)

1、Matplotlib 条形图 条形图或条状图是一种图表或图形&#xff0c;它显示带有矩形条的分类数据&#xff0c;其高度或长度与它们所代表的值成比例。可以垂直或水平绘制条形。 条形图显示了离散类别之间的比较。图表的一个轴显示要比较的特定类别&#xff0c;另一个轴表示测量值…

【python】PyQt5初体验,窗口等组件开发技巧,面向对象方式开发流程实战

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

国外开源字典集(wordlists)

Assetnote Wordlists Wordlists that are up to date and effective against the most popular technologies on the internet.https://wordlists.assetnote.io/

windows系统停止更新办法

windows系统停止更新 双击启动下载的文件 然后再回到系统-更新这里&#xff0c;选择日期就行。

RK3568技术笔记十四 Ubuntu创建共享文件夹

单击“虚拟机”&#xff0c;单击“设置”&#xff0c;如图所示&#xff1a; 单击“选项”&#xff0c;选择“总是启用&#xff08;E&#xff09;”&#xff0c;单击“添加”&#xff0c;如图所示&#xff1a; 单击“下一步”&#xff0c;如图所示&#xff1a; 单击“浏览”添加…

4LPFA清洗桶带隔板ICP-MS分析清洗系统高洁净特氟龙清洗设备

小瓶清洗系统PFA清洗桶品牌&#xff1a;南京瑞尼克 材质&#xff1a;PFA 耐受温度范围&#xff1a;-200C~260C 小瓶清洗系统是清洗实验室器皿有效的方法。该清洗系统由高纯PFA材质制成&#xff0c;专为热浸泡清洗设计&#xff0c;与传统玻璃烧杯相比&#xff0c;更结实。该小…

【笔记】打卡01 | 初学入门

初学入门:01-02 01 基本介绍02 快速入门库处理数据集网络构建模型训练保存模型加载模型打卡-时间 01 基本介绍 MindSpore Data&#xff08;数据处理层&#xff09; ModelZoo&#xff08;模型库&#xff09; MindSpore Science&#xff08;科学计算&#xff09;&#xff0c;包含…

Chromium 调试指南2024 Mac篇 - 调试 Chromium(三)

1.引言 在完成了环境准备和成功编译Chromium之后&#xff0c;下一步就是进行调试工作。调试是软件开发过程中必不可少的环节&#xff0c;通过调试可以定位和修复代码中的问题&#xff0c;验证新功能的正确性&#xff0c;并确保整个项目的稳定性和高效性。 由于Chromium项目的…

【html】如何利用hbuilderX 开发一个自己的app并安装在手机上运行

引言&#xff1a; 相信大家都非常想开发一款自己的apk&#xff0c;手机应用程序&#xff0c;今天就教大家&#xff0c;如何用hbuilderX 开发一个自己的app并安装在手机上运行。 步骤讲解&#xff1a; 打开hbuilderX &#xff0c;选择新建项目 2.选择5app,想一个名字&#x…

每天写java到期末考试(6.21)--集合4--练习--6.20

练习1&#xff1a; 正常写集合 bool类 代码&#xff1a; import QM_Fx.Student;import java.util.ArrayList;public class test {public static void main(String[] args) {ArrayList<Student> listnew ArrayList<>();//2.创建学生对象Student s1new Student(&quo…

从媒体网站的频道划分看媒体邀约的分类?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 媒体宣传加速季&#xff0c;100万补贴享不停&#xff0c;一手媒体资源&#xff0c;全国100城线下落地执行。详情请联系胡老师。 在我们举行活动的时候&#xff0c;通常会邀请媒体到现场来…

基于Python爬虫的城市天气数据可视化分析

基于Python爬虫的城市天气数据可视化分析 一、项目简介二、项目背景三、Python语言简介四、网络爬虫简介五、数据可视化简介六、天气数据爬取与存储6.1 获取目标网页6.2 发送请求6.3 提取数据6.4 保存数据七、天气数据可视化7.1 天气现象轮播图7.2 历史温度分布图7.3 历史风向分…

2134名女性,0感染!艾滋病预防药传出大消息,只需半年注射一次,药厂股价应声暴涨

内容提要 美国生物制药公司吉利德科学公布了Lenacapavir预防艾滋病毒的实验结果&#xff0c;显示出100%有效性。或将为艾滋病预防带来新选择。 文章正文 当地时间周四&#xff08;6月20日&#xff09;&#xff0c;美国生物制药公司吉利德科学在其官网公布一则重磅实验结果&am…

使用mysql的binlog进行数据恢复

1.mysql安装环境 在你本地电脑windows上建一个和生产环境一样的mysql版本 我的是 mysql5.7.43 安装教程可以自行上网搜&#xff08;这里不做介绍&#xff09; 可参考&#xff1a; 1.1安装路径 我的mysql安装路径&#xff1a; D:\mysql\mysql-5.7.43-winx64\bin * 1.2my.in…

官方解决 maven 上传jar包到中央仓库401

目录 目录背景&#xff1a;报错现象一句话解决一句话原因问题描述前车之鉴&#xff1a;尝试无果的记录尝试1&#xff1a;询问 GPT 未果尝试2&#xff1a;搜索引擎未果 正确原因分析&#xff1a;佐证 解决方案&#xff08;三步完成&#xff09;&#xff1a;1. 打开 sonatype2. 生…

MacOS设备远程登录配置结合内网穿透实现异地ssh远程连接

文章目录 前言1. MacOS打开远程登录2. 局域网内测试ssh远程3. 公网ssh远程连接MacOS3.1 MacOS安装配置cpolar3.2 获取ssh隧道公网地址3.3 测试公网ssh远程连接MacOS 4. 配置公网固定TCP地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址 5. 使用固定TCP端口地址ssh远程 …