当前位置: 首页 > news >正文

动态规划(基础)

一,背包问题

老规矩,上链接(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)

相关文章:

动态规划(基础)

一&#xff0c;背包问题 老规矩&#xff0c;上链接&#xff08;http://t.csdn.cn/hEwvu&#xff09; &#xff08;1&#xff09;01背包问题 给定一个承重量为C的背包&#xff0c;n个重量分别为w1​,w2​,...,wn​的物品&#xff0c;物品i放入背包能产生pi​(>0)的价值(i1,…...

【Pytorch:nn.Embedding】简介以及使用方法:用于生成固定数量的具有指定维度的嵌入向量embedding vector

文章目录 1、nn.Embedding2、使用场景 1、nn.Embedding 首先我们讲解一下关于嵌入向量embedding vector的概念 1&#xff09;在自然语言处理NLP领域&#xff0c;是将单词、短语或其他文本单位映射到一个固定长度的实数向量空间中。嵌入向量具有较低的维度&#xff0c;通常在几…...

动态库的命名规则

1、动态库的命名规则&#xff1a;libname.so.x.y.z 名字含义lib这是共享库的前缀name共享库名字x主版本号y次版本号z发布版本号 2、每个版本号的含义 版本号含义主版本号表示库的重大升级&#xff0c;不同主版本号的库之间是不兼容的。依赖旧的主版本号的程序需要改动相应的…...

【Linux】网络---->网络理论

网络理论 网络协议分层模型网络数据的封装于分用地址管理 网络协议分层模型 OSI五层模型&#xff1a;应用层&#xff0c;传输层&#xff0c;网络层&#xff0c;数据链路层&#xff0c;物理层 应用层&#xff1a;主要负责应用程序间的沟通&#xff0c;代表协议有HTML协议&#x…...

Android学习之路(4) UI控件之输入框

本节引言&#xff1a; 在本节中&#xff0c;我们来学习第二个很常用的控件EditText(输入框)&#xff1b; 和TextView非常类似&#xff0c;最大的区别是&#xff1a;EditText可以接受用户输入&#xff01; 1.设置默认提示文本 如下图&#xff0c;相信你对于这种用户登录的界面并…...

1.初识Web

文章目录 1. 什么是Web?2.初始Web前端2.1.Web标准 1. 什么是Web? web:全球广域网&#xff0c;也称万维网(www World Wide Web)&#xff0c;能够通过浏览器访问的网站。 2.初始Web前端 网页有哪些部分组成&#xff1f; 文字、图片、音频、视频、超链接… 我们看到的网页&am…...

【微服务技术一】Eureka、Nacos、Ribbon(配置管理、注册中心、负载均衡)

微服务技术一 技术栈图一、注册中心Eureka概念&#xff1a;搭建EurekaServer服务注册服务发现&#xff08;消费者对提供者的远程调用&#xff09; 二、Ribbon负载均衡负载均衡的原理&#xff1a;LoadBalanced负载均衡的策略&#xff1a;IRule懒加载 三、Nacos注册中心Nacos的安…...

【Linux】可重入函数 volatile关键字 以及SIGCHLD信号

可重入函数 volatile关键字 以及SIGCHLD信号 一、可重入函数1、引入2、可重入函数的判断 二、volatile关键字1、引入2、关于编译器的优化的简单讨论 三、SIGCHLD信号 一、可重入函数 1、引入 我们来先看一个例子来帮助我们理解什么是可重入函数&#xff1a; 假设我们现在要对…...

【动态规划】回文串问题

文章目录 动态规划&#xff08;回文串问题&#xff09;1. 回文子串2. 最长回文子串3. 回文串分割 IV4. 分割回文串 ||5. 最长回文子序列6. 让字符串成为回文串的最小插入次数 动态规划&#xff08;回文串问题&#xff09; 1. 回文子串 题目链接 状态表示 f[i][j]表示 i 到 j …...

Laravel Swift Mail发送带附件的邮件报错 “Swift_IoException The path cannot be empty“处理

先说下情况&#xff0c;就是我要做一个发送附件的邮件发送功能&#xff0c;结果&#xff0c;报错&#xff1a;The path cannot be empty。给我整的有点迷糊&#xff0c;网上也没有类似的问题。后来&#xff0c;我检查了一下代码&#xff0c;发现有个地方&#xff0c;是需要给附…...

Linux下常见的代理服务器软件介绍

在Linux系统中&#xff0c;代理服务器是我们搭建网络环境和处理网络请求的常用工具。但是&#xff0c;你知道Linux下常见的代理服务器软件有哪些吗&#xff1f;本文将为你带来对几款常见的Linux代理服务器软件的介绍&#xff0c;帮助你选择适合的代理服务器。 一、Squid&#…...

SCSS的基本用法

1、声明变量 $ 声明变量的符号 $ 下面这张图左半部分是scss的语法&#xff0c;右半部分是编译后的css。&#xff08;整篇文章皆是如此&#xff09; 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列表&#xff0c;相当于Java中的list集合。特点&#xff1a;元素有序 且 可以重复。 3.2、内存存储模型 3.3、常用…...

四大运营商的大流量卡测评,看完您会选哪个运营商?

很多朋友都说网上的流量卡资费是真的便宜&#xff0c;但是小编认为资费便宜归便宜&#xff0c;但是运营商的小心思也有不少。 ​ 今天小编就带大家看一看三大运营商推出的正规流量卡都有哪些小心思&#xff1f; 首先&#xff0c;移动推出的线上大流量卡数量是最少的&#xff…...

Apache-Maven

安装Maven 解压apache-maven到目录下 Maven目录如下 bin&#xff1a;目录中存放的是可执行文件&#xff0c;JAVA项目中的编译执行打包都要使用bin. conf:存放的是Maven的配置文件&#xff0c;本地配置、私服配置都需要在conf下的settings.xml进行配置。 lib下存放的是Maven所…...

什么是原子交换?

安全地在各个区块链网络之间传输资产对于释放被困流动性并吸引更多用户进入这一领域至关重要&#xff0c;同时也保持 Web3 的信任最小化核心价值。原子交换是一种让两个人在不依赖于中介来促成交易的情况下&#xff0c;在不同的区块链网络之间交换通证资产的方式。这为 DeFi 用…...

java springboot word文档转pdf

java springboot word文档转pdf 1、环境2、依赖3、代码 1、环境 1、java、springboot 2、maven或者gradle 3、办公软件&#xff08;自己电脑上的wps或者office等&#xff0c;如果部署到服务器上也要安装&#xff0c;linux、Mac 都有&#xff0c;自己安装&#xff09; 可能会遇…...

【Leetcode Sheet】Weekly Practice 2

Leetcode Test 1281 整数的各位积和之差(8.9) 给你一个整数 n&#xff0c;请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。 提示&#xff1a; 1 < n < 10^5 【原始代码】&#xff1a; int subtractProductAndSum(int n){//1 < n < 10^5//…...

【BERTopic应用 03/3】:微调参数

一、说明 一般来说&#xff0c;BERTopic 在开箱即用的模型中工作得很好。但是&#xff0c;当您有数百万个数据要处理时&#xff0c;使用基本模型处理数据可能需要一些时间。在这篇文章中&#xff0c;我将向您展示如何微调BERTopic中的一些参数并比较它们的结果。让我们潜入。 二…...

图卷积网络代码规范:PyGCN项目Python风格与最佳实践终极指南

图卷积网络代码规范&#xff1a;PyGCN项目Python风格与最佳实践终极指南 【免费下载链接】pygcn Graph Convolutional Networks in PyTorch 项目地址: https://gitcode.com/gh_mirrors/py/pygcn 图卷积网络&#xff08;Graph Convolutional Networks, GCN&#xff09;是…...

Qwen3.5-9B-AWQ-4bit Java开发环境快速配置:从安装到第一个AI程序

Qwen3.5-9B-AWQ-4bit Java开发环境快速配置&#xff1a;从安装到第一个AI程序 1. 准备工作&#xff1a;你需要什么 在开始之前&#xff0c;确保你的电脑满足以下基本要求&#xff1a; 操作系统&#xff1a;Windows 10/11、macOS 10.15 或主流Linux发行版内存&#xff1a;至少…...

收藏!小白/程序员转行Agent必看,4步理清学习思路,轻松具备求职竞争力

如今&#xff0c;AI领域的风口早已到来&#xff0c;Agent作为当下最热门的赛道之一&#xff0c;掌握其相关技能&#xff0c;无疑能让你在就业市场中脱颖而出&#xff0c;成为企业争抢的核心人才。无论是刚入门的编程小白&#xff0c;还是想转型的资深程序员&#xff0c;Agent都…...

Arduino红外遥控库:让硬件设备听懂遥控器的语言

Arduino红外遥控库&#xff1a;让硬件设备听懂遥控器的语言 【免费下载链接】Arduino-IRremote Infrared remote library for Arduino: send and receive infrared signals with multiple protocols 项目地址: https://gitcode.com/gh_mirrors/ar/Arduino-IRremote 你是…...

RTX4090D优化版Qwen3-32B+OpenClaw实战:低成本构建个人AI工作流

RTX4090D优化版Qwen3-32BOpenClaw实战&#xff1a;低成本构建个人AI工作流 1. 为什么选择本地部署大模型OpenClaw组合 去年我开始尝试用AI自动化处理日常工作&#xff0c;最初直接调用公有云API&#xff0c;但很快遇到三个痛点&#xff1a;一是敏感文件不敢上传第三方服务&am…...

快速验证CNN结构:用快马平台一键生成手写数字识别原型

快速验证CNN结构&#xff1a;用快马平台一键生成手写数字识别原型 最近在学深度学习&#xff0c;想试试用卷积神经网络(CNN)做个手写数字识别的小项目。传统从零开始写代码太费时间了&#xff0c;光是搭环境、调参数就能折腾半天。后来发现InsCode(快马)平台能直接生成可运行的…...

书匠策AI:学术江湖里的“论文剑客”,助你披荆斩棘!

书匠策AI官网&#xff1a;www.shujiangce.com | 微信公众号搜一搜&#xff1a;书匠策AI 在学术的江湖里&#xff0c;写期刊论文就像是一场“闯关游戏”——选题、查文献、搭框架、写内容、调格式……每一关都充满挑战&#xff0c;稍有不慎就可能“Game Over”。但别怕&#xf…...

Windows下OpenClaw安装避坑:千问3.5-9B接口配置详解

Windows下OpenClaw安装避坑&#xff1a;千问3.5-9B接口配置详解 1. 为什么选择WindowsOpenClaw组合 作为一个长期在Windows环境下工作的开发者&#xff0c;我一直在寻找能够提升日常效率的自动化工具。直到遇到OpenClaw&#xff0c;这个开源的AI智能体框架彻底改变了我的工作…...

HoYo-Glyphs:11款米哈游游戏文字字体,轻松打造你的专属游戏世界

HoYo-Glyphs&#xff1a;11款米哈游游戏文字字体&#xff0c;轻松打造你的专属游戏世界 【免费下载链接】HoYo-Glyphs Constructed scripts by HoYoverse 米哈游的架空文字 项目地址: https://gitcode.com/gh_mirrors/ho/HoYo-Glyphs 你是否曾被《原神》中蒙德教堂的哥特…...

Nanbeige4.1-3B代码实例:用pipeline接口封装推理服务,支持HTTP API调用

Nanbeige4.1-3B代码实例&#xff1a;用pipeline接口封装推理服务&#xff0c;支持HTTP API调用 1. 引言 如果你正在寻找一个既小巧又强大的开源语言模型&#xff0c;Nanbeige4.1-3B绝对值得你花时间了解一下。这个只有30亿参数的模型&#xff0c;在推理、代码生成和对话任务上…...