动态规划(基础)
一,背包问题
老规矩,上链接(http://t.csdn.cn/hEwvu)
(1)01背包问题
给定一个承重量为C的背包,n个重量分别为w1,w2,...,wn的物品,物品i放入背包能产生pi(>0)的价值(i=1,2,...,n)。每个物品要么整个放入背包,要么不放。要求找出最大价值的装包方案。
输入格式:
输入的第一行包含两个正整数n和C(1≤n≤20),第二行含n个正整数分别表示n个物品的重量,第三行含n个正整数分别表示n个物品放入背包能产生的价值。
输出格式:
在一行内输出结果,包括最大价值装包方案的价值、具体装包方案,用空格隔开。具体装包方案是n个物品的一个子集,用长度为n的0、1串表示(1表示对应物品被选中,0表示没有被选中)。如果这样的0、1串不唯一,取字典序最大的那个串。
输入样例:
4 9
2 3 4 5
3 4 5 7
输出样例:
12 1110
(注:1110 和0011都是价值最大的装包方案,取字典序最大的结果即为1110)
思想:最最经典的dp问题,画个图就明白了。

AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int dp[N][N], w[N], val[N];int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i];//重量for (int i = 1; i <= n; i++) cin >> val[i];//价值//求最大价值for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + val[i]);else dp[i][j] = dp[i - 1][j];}}cout << dp[n][m] << endl;//打印字典序for (int i = 1; i <= n; i++) {if (dp[i][m] - dp[i - 1][m] == 0) cout << "0";else cout << "1";}return 0;
}
利用滚动数组优化,将二维数组降为一维数组
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N], t[N], val[N];int main()
{int time, n;cin >> time >> n;for (int i = 1; i <= n; i++) cin >> t[i] >> val[i];for (int i = 1; i <= n; i++) {//时间为j时的最大价值for (int j = time; j >= t[i]; j--) {//这里j倒序是为了防止重复拿同一件物品dp[j] = max(dp[j], dp[j - t[i]] + val[i]);}}cout << dp[time] << endl;return 0;
}
(2)完全背包问题
有一个容积为 V 的背包,同时有 n 种物品,每种物品均有各自的体积 w 和价值 v,每种物品的数量均为无限个,求使用该背包最多能装的物品价值总和。
疯狂的采药 - 洛谷
思路:我们此时在多家一重循环表示同一种物品的数量就可以了,那么我们的递推式就变为
dp[i][j] = max( dp[i-1][j] , dp[i-1][ j - k*w[i] ] + k*v[i] )
AC代码
#include<iostream>
using namespace std;const int N=1005;
const int M=105;
int n,m,maxValue,temp;
int dp[M][N],t[M],v[M];int main()
{cin>>n>>m;for(int i=1;i<=m;i++) cin>>t[i]>>v[i];for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){maxValue=0;for(int k=0;k*t[i]<=j;k++){temp=dp[i-1][j-k*t[i]]+k*v[i];if(temp>maxValue) maxValue=temp;}dp[i][j]=maxValue;}cout<<dp[m][n]<<endl;return 0;
}
这段代码是不能通过测试的,因为本题的数据比较大,而且我们用了三重循环,时间复杂度比较高,所以此方法不行。
同样的,我们使用滚动数组进行优化。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
long long dp[N], t[N], val[N];//数据过大,开长整型int main()
{int time, n;cin >> time >> n;for (int i = 1; i <= n; i++) cin >> t[i] >> val[i];for (int i = 1; i <= n; i++) {for (int j = t[i]; j <=time; j++) {dp[j] = max(dp[j], dp[j - t[i]] + val[i]);}}cout << dp[time] << endl;return 0;
}
(3)
相关文章:
动态规划(基础)
一,背包问题 老规矩,上链接(http://t.csdn.cn/hEwvu) (1)01背包问题 给定一个承重量为C的背包,n个重量分别为w1,w2,...,wn的物品,物品i放入背包能产生pi(>0)的价值(i1,…...
【Pytorch:nn.Embedding】简介以及使用方法:用于生成固定数量的具有指定维度的嵌入向量embedding vector
文章目录 1、nn.Embedding2、使用场景 1、nn.Embedding 首先我们讲解一下关于嵌入向量embedding vector的概念 1)在自然语言处理NLP领域,是将单词、短语或其他文本单位映射到一个固定长度的实数向量空间中。嵌入向量具有较低的维度,通常在几…...
动态库的命名规则
1、动态库的命名规则:libname.so.x.y.z 名字含义lib这是共享库的前缀name共享库名字x主版本号y次版本号z发布版本号 2、每个版本号的含义 版本号含义主版本号表示库的重大升级,不同主版本号的库之间是不兼容的。依赖旧的主版本号的程序需要改动相应的…...
【Linux】网络---->网络理论
网络理论 网络协议分层模型网络数据的封装于分用地址管理 网络协议分层模型 OSI五层模型:应用层,传输层,网络层,数据链路层,物理层 应用层:主要负责应用程序间的沟通,代表协议有HTML协议&#x…...
Android学习之路(4) UI控件之输入框
本节引言: 在本节中,我们来学习第二个很常用的控件EditText(输入框); 和TextView非常类似,最大的区别是:EditText可以接受用户输入! 1.设置默认提示文本 如下图,相信你对于这种用户登录的界面并…...
1.初识Web
文章目录 1. 什么是Web?2.初始Web前端2.1.Web标准 1. 什么是Web? web:全球广域网,也称万维网(www World Wide Web),能够通过浏览器访问的网站。 2.初始Web前端 网页有哪些部分组成? 文字、图片、音频、视频、超链接… 我们看到的网页&am…...
【微服务技术一】Eureka、Nacos、Ribbon(配置管理、注册中心、负载均衡)
微服务技术一 技术栈图一、注册中心Eureka概念:搭建EurekaServer服务注册服务发现(消费者对提供者的远程调用) 二、Ribbon负载均衡负载均衡的原理:LoadBalanced负载均衡的策略:IRule懒加载 三、Nacos注册中心Nacos的安…...
【Linux】可重入函数 volatile关键字 以及SIGCHLD信号
可重入函数 volatile关键字 以及SIGCHLD信号 一、可重入函数1、引入2、可重入函数的判断 二、volatile关键字1、引入2、关于编译器的优化的简单讨论 三、SIGCHLD信号 一、可重入函数 1、引入 我们来先看一个例子来帮助我们理解什么是可重入函数: 假设我们现在要对…...
【动态规划】回文串问题
文章目录 动态规划(回文串问题)1. 回文子串2. 最长回文子串3. 回文串分割 IV4. 分割回文串 ||5. 最长回文子序列6. 让字符串成为回文串的最小插入次数 动态规划(回文串问题) 1. 回文子串 题目链接 状态表示 f[i][j]表示 i 到 j …...
Laravel Swift Mail发送带附件的邮件报错 “Swift_IoException The path cannot be empty“处理
先说下情况,就是我要做一个发送附件的邮件发送功能,结果,报错:The path cannot be empty。给我整的有点迷糊,网上也没有类似的问题。后来,我检查了一下代码,发现有个地方,是需要给附…...
Linux下常见的代理服务器软件介绍
在Linux系统中,代理服务器是我们搭建网络环境和处理网络请求的常用工具。但是,你知道Linux下常见的代理服务器软件有哪些吗?本文将为你带来对几款常见的Linux代理服务器软件的介绍,帮助你选择适合的代理服务器。 一、Squid&#…...
SCSS的基本用法
1、声明变量 $ 声明变量的符号 $ 下面这张图左半部分是scss的语法,右半部分是编译后的css。(整篇文章皆是如此) 2、默认变量 !default sass 的默认变量仅需要在值后面加上 !default 即可。 如果分配给变量的值后面添加了 !default 标志…...
alertmanager创建nginx-ingress basic auth鉴权
步骤 生成密码 printf "admin:$(openssl passwd -crypt xxxxxx)\n" >> auth 创建新的 Kubernetes 密钥 kubectl create secret generic basic-auth --from-file auth -n victoria-metrics 修改 ingress 以使用 secret 中的凭证来实现基本身份验证 编辑 P…...
系列六、Redis中的五大数据类型及相关操作
一、五大数据类型 String类型、List类型、Set类型、ZSet类型、hash类型。 二、String类型 2.1、内存储存模型 2.2、常用操作命令 三、List类型 3.1、概述 list列表,相当于Java中的list集合。特点:元素有序 且 可以重复。 3.2、内存存储模型 3.3、常用…...
四大运营商的大流量卡测评,看完您会选哪个运营商?
很多朋友都说网上的流量卡资费是真的便宜,但是小编认为资费便宜归便宜,但是运营商的小心思也有不少。 今天小编就带大家看一看三大运营商推出的正规流量卡都有哪些小心思? 首先,移动推出的线上大流量卡数量是最少的ÿ…...
Apache-Maven
安装Maven 解压apache-maven到目录下 Maven目录如下 bin:目录中存放的是可执行文件,JAVA项目中的编译执行打包都要使用bin. conf:存放的是Maven的配置文件,本地配置、私服配置都需要在conf下的settings.xml进行配置。 lib下存放的是Maven所…...
什么是原子交换?
安全地在各个区块链网络之间传输资产对于释放被困流动性并吸引更多用户进入这一领域至关重要,同时也保持 Web3 的信任最小化核心价值。原子交换是一种让两个人在不依赖于中介来促成交易的情况下,在不同的区块链网络之间交换通证资产的方式。这为 DeFi 用…...
java springboot word文档转pdf
java springboot word文档转pdf 1、环境2、依赖3、代码 1、环境 1、java、springboot 2、maven或者gradle 3、办公软件(自己电脑上的wps或者office等,如果部署到服务器上也要安装,linux、Mac 都有,自己安装) 可能会遇…...
【Leetcode Sheet】Weekly Practice 2
Leetcode Test 1281 整数的各位积和之差(8.9) 给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。 提示: 1 < n < 10^5 【原始代码】: int subtractProductAndSum(int n){//1 < n < 10^5//…...
【BERTopic应用 03/3】:微调参数
一、说明 一般来说,BERTopic 在开箱即用的模型中工作得很好。但是,当您有数百万个数据要处理时,使用基本模型处理数据可能需要一些时间。在这篇文章中,我将向您展示如何微调BERTopic中的一些参数并比较它们的结果。让我们潜入。 二…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...
