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取1dp[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.rhkb.cn/news/355475.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

队列 + 宽搜(BFS)

例题一 解法&#xff1a; 算法思路&#xff1a; 层序遍历即可~ 仅需多加⼀个变量&#xff0c;⽤来记录每⼀层结点的个数就好了。 例题二 解法&#xff08;层序遍历&#xff09;&#xff1a; 算法思路&#xff1a; 在正常的层序遍历过程中&#xff0c;我们是可以把⼀层的结点…

SpringBoot整合justauth实现多种方式的第三方登陆

目录 0.准备工作 1.引入依赖 2.yml文件 3. Controller代码 4.效果 参考 0.准备工作 你需要获取三方登陆的client-id和client-secret 以github为例 申请地址&#xff1a;Sign in to GitHub GitHub 1.引入依赖 <?xml version"1.0" encoding"UTF-8&quo…

行车记录仪文件夹“0字节”现象解析与恢复策略

一、行车记录仪文件夹“0字节”现象描述 行车记录仪作为现代驾驶中的必备设备&#xff0c;其储存的视频数据对于事故记录和取证至关重要。然而&#xff0c;有时车主们可能会遇到这样一个问题&#xff1a;行车记录仪的某个文件夹内的文件突然变成了0字节大小&#xff0c;无法正…

用于快速充电站的 AC/DC 转换器概述

电动汽车构成了未来实现可持续交通部门的有前途技术的主要部分。AC/DC 转换器是扩展和改进 EV 功能的骨干组件。本文概述了 AC/DC 转换器、充电站类型、传统两电平 (2L) AC/DC 转换器面临的问题以及使用多电平转换器 (MLC) 的重要性。 AC/DC 充电器示意图&#xff08;&#xff…

北航数据结构与程序设计图部分选填题

一、 抓两个关键信息&#xff1a;无向图&#xff0c;邻接表。无向图中&#xff0c;边&#xff08;vi&#xff0c;vj&#xff09;要在vi的链表中记录一次&#xff0c;再以&#xff08;vj&#xff0c;vi&#xff09;的形式在vj的链表中记录一次。 每个边都要记录两次&#xff0c…

Linux机器通过Docker-Compose安装Jenkins发送Allure报告

目录 一、安装Docker 二、安装Docker Compose 三、准备测试用例 四、配置docker-compose.yml 五、启动Jenkins 六、配置Jenkins和Allure插件 七、创建含pytest的Jenkins任务 八、项目结果通知 1.通过企业微信通知 2.通过邮件通知 九、配置域名DNS解析 最近小编接到一…

Ollama深度探索:AI大模型本地部署的全面教程

目录 引言一、Ollama概述1、定义与定位2、核心功能3、技术优势4、应用场景 二、安装与配置1、系统要求2、安装方法3、配置指南4、启动Ollama服务 四、快速开始1、启动Ollama2、部署运行模型3、REEST API 五、自定义模型1、定制化的必要性2、使用Modelfile定制模型3、参数调整4、…

FPGA的基础仿真项目--七段数码管设计显示学号

一、设计实验目的 1&#xff0e; 了解数码管显示模块的工作原理。 2&#xff0e; 熟悉VHDL 硬件描述语言及自顶向下的设计思想。 3&#xff0e; 掌握利用FPGA设计6位数码管扫描显示驱动电路的方法。 二、实验设备 1. PC机 2.Cyclone IV FPGA开发板 三、扫描原理 下图所…

OSPF被动接口配置(华为)

#交换设备 OSPF被动接口配置 一、基本概念 OSPF被动接口&#xff0c;也称为抑制接口&#xff0c;即将路由器某一接口配置为被动接口后&#xff0c;该接口不会再接受和发送OSPF报文 二、使用场景 在路由器与终端相近或者直接相连的一侧配置被动接口 因为OSPF会定期发送报文…

【分类讨论】899. 有序队列

本文涉及知识点 分类讨论 LeetCode899. 有序队列 给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个&#xff0c;并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后&#xff0c;字典序最小的字符串 。 示例 1&#xff1a; 输入&#xff1…

数据库设计文档编写

方法1&#xff1a;使用 Navicat 生成数据库设计文档 效果 先看简单的效果图&#xff0c;如果效果合适&#xff0c;大家在进行测试使用&#xff0c;不合适直接撤退&#xff0c;也不浪费时间。 随后在docx文档中生成目标字段的表格&#xff0c;选中全部(ctrla)进行复制(ctrlc)…

《Cloud Native Data Center Networking》(云原生数据中心网络设计)读书笔记 -- 02 Clos拓扑

本章回答以下问题&#xff1a; 什么是 Clos 拓扑&#xff0c;它与“接入 - 汇聚 - 核心”拓扑有何不同?Clos 拓扑的特征是什么?Clos 拓扑对数据中心网络的影响是什么? Clos拓扑 云原生数据中心基础设施的先行者们想要构建一种支持大规模水平扩展网络。 基本的Clos拓扑如图…

AI日报|我国人工智能核心产业规模已达5784亿元!阿里通义Qwen2成斯坦福大模型榜单最强开源模型!

⭐️搜索“可信AI进展“关注公众号&#xff0c;动手做AI Agent书籍&#xff0c;限量免费赠送&#xff01;快来参与吧&#xff5e; 文章链接&#xff1a; 福利来啦&#xff01;动手做AI Agent书籍&#xff0c;限量免费赠送&#xff01; 今日热点&#xff1a; 我国人工智能企业…

【2024亲测无坑】在Centos.7虚拟机上安装Oracle 19C

目录 一、安装环境准备 1、linux虚拟机安装 2、虚拟机快照 3、空间检查&软件上传 二、Oracle软件安装 1.preinstall安装及其他配置准备 2.oracle安装 三、数据库实例的安装 1.netca——网络配置助手 2.dbca——数据库配置助手 四、ORACLE 19C 在linux centos 7上…

Windows环境部署MySQL_8.4.0 LTS的部署安装、验证连接以及卸载全过程实操手册

前言&#xff1a; 什么是 MySQL MySQL 是一个关系型数据库管理系统&#xff0c;由瑞典 MySQL AB 公司开发&#xff0c;目前属于Oracle 公司。MySQL 是一种关系型数据库管理系统&#xff0c;关系型数据库将数据保存在不同的表中&#xff0c;而不是将所有数据放在一个大仓库内&am…

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

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

双写一致性

双写一致性 当修改了数据库的数据也要同时更新缓存的数据&#xff0c;缓存和数据库的数据要保持一致。 注意这里是对数据库进行写操作而不是读操作&#xff0c;通常我们有两种方式完成这个写操作&#xff0c;分别是&#xff1a;先删除缓存再修改数据库 和 先修改数据库再删除…

SAP FICO 下载文件报错【调用数据提供商错误】

报错如下图所示&#xff1a; 解决办法&#xff1a; 当弹出保存文件的提示时&#xff0c;不要点击“记住我的决定”

qemu 安装ubuntu22.04虚拟机 -纯命令行-可ssh-带网络-编译安装 linux kernel-编译安装 kernel module

1&#xff0c;预备系统盘数据 1.1 下载光盘 注意需要 liver-server $ wget https://releases.ubuntu.com/22.04.4/ubuntu-22.04.4-live-server-amd64.iso 1.2 挂载并拷贝 $ sudo mkdir /mnt/iso_ubuntu-22.04.4-live-server-amd64 $ sudo mount ubuntu-22.04.4-live-ser…

蔚来汽车AI算法工程师,如何理解注意力?

大家好啊&#xff0c;我是董董灿。 今天分享一个上海蔚来汽车的AI算法岗位面试经验总结帖&#xff0c;面试岗位为算法工程师。 这次面试提到的问题&#xff0c;除了与实习相关内容和反问之外&#xff0c;面试官总共问了8个问题&#xff0c;主要集中在深度学习基础概念的理解上…