【背包题】oj题库

目录

1282 - 简单背包问题

1780 - 采灵芝

1888 - 多重背包(1)​编辑

1891 - 开心的金明

2073 - 码头的集装箱

1905 - 混合背包


1282 - 简单背包问题

#include <bits/stdc++.h>
using namespace std;
//二维数组:dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
//一维数组滚动优化:
//状态转移方程:dp[j]=max(dp[j],v[i]+dp[j-w[i]])
int w;//背包容量
int dp[20010];
int n,wi,vi;int main() {cin>>w>>n;//遍历每个物品for(int i=1; i <= n; i++) {cin>>wi>>vi;
//倒过来循环for(int j=w; j>= wi; j--) {
//讨论每个物品选和不选的两个状态
//取能到的价值的最大值dp[j]= max(dp[j],dp[j-wi]+ vi);}}cout<<dp[w];return 0;
}
#include <bits/stdc++.h>
using namespace std;//动态转移方程:dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
//c:代表背包容量
//dp[i][j]:有i件物品,背包容量为了的情况下存储的最大价值
int c,dp[110][20100],w[110],v[110],i,j,n;
int main() {
//读入cin>>c>>n;for(i =1; i<= n; i++) {cin>>w[i]>>v[i];}//递推求 dp 数组//i:代表物品数量for(i = 1; i <= n; i++) {//在i件物品,讨论背包容量分别是1~c的情况下,最大价值//j:代表背包容量for(j= 1; j<= c; j++) {//如果能放得下if(w[i]<= j) {dp[i][j]= max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);} else {//放不下dp[i][j]= dp[i-1][j];}}}//输出n件物品,背包容量为c的最大价值cout<<dp[n][c];return 0;
}

1780 - 采灵芝

#include <bits/stdc++.h>
using namespace std;/*完全背包状态转移方程
二维写法:f[i][j]= max(f[i-1]], f[i][j-w[i]]+v[])
一维写法:f[]j=max(f[j],f-w[i]]+v[i])
一维状态转义方程和01背包一致,要注意,完全背包要从前往后推导。*/
int t,m;
int f[100010];
int ti,vi;//每个物品的采摘时间和价值
int main() {cin>>t>>m;//读入m个物品 for(int i = 1; i<= m; i++) {cin>>ti>>vi;//正序循环 
//从当前物品的重量(采摘时间)~背包容量最大时间)循环for(int j = ti; j <= t; j++) {f[j] = max(f[j],f[j-ti]+vi);}}cout<<f[t];//背包能够存储的最大价值return 0;
}

1888 - 多重背包(1)

#include <bits/stdc++.h>
using namespace std;
/*01背包:每种物品有1件
完全背包:每种物品有无限件数多
重背包:每种物品有Si件
解题思路:将多重背包转换为01背包
将si件物品都存起来,转换为有si个物品,每个物品有1件*/
int n,c;//c背包容量
int v[10010],w[10010];
int dp[110];
int vi,wi,si,k;//k代表数组下标
int main() {cin>>n>>c;for(int i=1; i <= n; i++) {cin>>vi>>wi>>si;//第i个物品有si件,都存入数组for(int j=1; j<= si; j++) {k++;v[k]= vi;w[k]= wi;}}
//01 背包for(int i=1; i <= k; i++) { //逆序从背包容量循环到当前物品体积for(int j=c; j >= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[c];return 0;
}
#include <bits/stdc++.h>
using namespace std;
/*01背包:每种物品有1件
完全背包:每种物品有无限件数多
重背包:每种物品有Si件
解题思路:将多重背包转换为01背包
将si件物品都存起来,转换为有si个物品,每个物品有1件*/
int n,c;//c背包容量
int v[110],w[110],s[110];
int dp[110];int main() {cin>>n>>c;for(int i=1; i <= n; i++) {cin>>v[i]>>w[i]>>s[i];//第i个物品有si件,都存入数组}
//01 背包
//有n个物品for(int i=1; i<= n; i++) {for(int k=1; k<= s[i]; k++) {//逆序从背包容量循环到当前物品体积for(int j=c; j>= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}}
//	for(int i=1; i <= k; i++) {
//		//逆序从背包容量循环到当前物品体积
//		for(int j=c; j >= v[i]; j--) {
//			dp[j]= max(dp[j],dp[j-v[i]]+w[i]);
//		}
//	}cout<<dp[c];return 0;
}

1891 - 开心的金明

题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过NN元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的NN元。于是,他把每件物品规定了一个重要度,分为55等:用整数1-51−5表示,第55等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过NN元(可以等于NN元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第jj件物品的价格为v[j]v[j],重要度为w[j]w[j],共选中了kk件物品,编号依次为j_1,j_2,…,j_kj1​,j2​,…,jk​,则所求的总和为:

v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]v[j1​]×w[j1​]+v[j2​]×w[j2​]+…+v[jk​]×w[jk​]。

请你帮助金明设计一个满足要求的购物单。

#include <bits/stdc++.h>
using namespace std;int w[30],v[30],f[50000];
//w数组为重要度,v数组为money,f是用来dp的数组
int n,m;//n是总物品个数,m是总钱数
int main() {cin>>m>>n;//输入for(int i=1; i<=n; i++) {cin>>v[i]>>w[i];w[i]*=v[i];//v数组在这里意义变为总收获(重要度*money)}
//01背包(参照第二类模板“一维数组优化”for(int i=1; i<=n; i++) {for(int j=m; j>=v[i]; j--) {
//注意从m开始if(j>=v[i]) {f[j]=max(f[j],f[j-v[i]]+w[i]);//dp}}}cout<<f[m]<<endl;//背包大小为m时最大值return 0;
}

2073 - 码头的集装箱

题目描述

码头上停泊一艘远洋轮船,轮船可以装下 cc 吨的货物,码头上有 nn 个集装箱需要运走,已知第 ii 个集装箱的重量为w_iwi​。

请你编程计算,在不超出轮船最大载重量的情况下,该轮船最多可以运走多少吨的集装箱。(注意:单个集装箱不能拆开运送,对于每个集装箱来说,要么整个运到轮船上,要么不运)

#include <bits/stdc++.h>
using namespace std;int n,c,w;
int f[40000];
int main() {cin>>n>>c;for(int i = 1; i <= n; i++) {cin>>w;for(int j=c; j>=w; j--) {f[j] = max(f[j],f[j-w]+w);}}cout<<f[c];
return 0;
}

1905 - 混合背包

题目描述

有 NN 种物品和一个容量是 VV 的背包。

物品一共有三类:

  1. 第一类物品只能用 11 次(01背包);

  2. 第二类物品可以用无限次(完全背包);

  3. 第三类物品最多只能用 s_isi​ 次(多重背包);

每种体积是 v_ivi​,价值是 w_iwi​。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

输出最大价值。

#include <bits/stdc++.h>
using namespace std;
const int N=20000;
int v[N],w[N],s[N];
int vi,wi,si;
int k=0;//表示存入数组的数据量
int dp[1010];
int n,m;
int main() {cin>>n>>m;for(int i=1; i<= n; i++) {cin>>vi>>wi>>si;//如果是多重背包,做二进制拆分if(si > 0) {int t=1;while(t<= si) {k++;w[k]= t * wi;v[k]= t * vi;s[k]=-1;//转换为 01 背包si= si -t;t= t * 2;}if(si >0) {k++;w[k]= si * wi;v[k]= si * vi;s[k]=-1;//01背包}} else {k++;w[k]= wi;v[k]= vi;s[k]= si;}}
//计算//循环k个物品for(int i=1; i<= k; i++) { //判断是01背包还是完全背包if(s[i]== -1) {for(int j= m; j >= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}} else {for(int j = v[i]; j<= m; j++) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}}cout<<dp[m];return 0;
}

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

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

相关文章

父亲节马上到了-和我一起用Python写父亲节的祝福吧

前言 让我们一起用Python写一段父亲节的祝福吧 &#x1f4dd;个人主页→数据挖掘博主ZTLJQ的主页 个人推荐python学习系列&#xff1a; ☄️爬虫JS逆向系列专栏 - 爬虫逆向教学 ☄️python系列专栏 - 从零开始学python 话不多说先上代码 import tkinter as tk from doctest imp…

宠物健康顾问系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;顾问管理&#xff0c;用户管理&#xff0c;健康知识管理&#xff0c;管理员管理&#xff0c;论坛管理&#xff0c;公告管理 顾问账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;顾…

深入理解计算机系统 CSAPP 家庭作业6.36

A:100% 数组x的大小是缓存的两倍, x[0][0]-x[0][127]刚好存满512字节,那就意味着x[1][0]映射在缓存的组0,那就意味着x[0][i]和x[1][i]总是读到缓存后又互相替换. B:25% 缓存变为1024字节,意味着x[1][0]被映射在缓存的组128 (组0到127存放x[0][0]到x[0][127]),所以每次读一行…

企业网站建设方案

企业网站建设方案是企业推广和宣传的重要工具&#xff0c;可以帮助企业树立良好的形象&#xff0c;吸引更多的客户和合作伙伴。一个好的企业网站应该具备用户友好的界面设计、快速的加载速度、完善的信息分类和搜索功能、优质的内容和多样化的互动体验。下面将从以下几个方面介…

Python使用策略模式生成TCP数据包

使用策略模式&#xff08;Strategy Pattern&#xff09;来灵活地生成不同类型的TCP数据包。 包括三次握手、数据传输和四次挥手。 from scapy.all import * from scapy.all import Ether, IP, TCP, UDP, wrpcap from abc import ABC, abstractmethodclass TcpPacketStrategy(A…

flink standalone部署模式

standalone模式可以在单台机器以不同进程方式启动&#xff0c;也可以以多机器分布式方式启动。 任务的提交模式有三种&#xff1a;application mode、session model、per-job mode&#xff08;1.4x版本后过时&#xff09;。 注意区分任务的提交模式与集群的部署模式区别。 以…

C++语法05 浮点型/实数类型

什么是实数类型 实数类型是一种数据类型&#xff0c;实数类型变量里能存放小数和整数。 定义格式&#xff1a;double a; 赋值&#xff1a;a0.4; 输入&#xff1a;cin>>a; 输出&#xff1a;cout<<a; 训练&#xff1a;尺子的价格 小知在文具店买铅笔&#xff…

springmvc 全局异常处理器配置的三种方式深入底层源码分析原理

文章目录 springmvc 全局异常处理器配置的三种方式&深入底层源码分析原理配置全局异常处理器的三种方式实现接口HandlerExceptionResolver并配置到WebMvcConfigurer注解式配置ExceptionHandlercontroller里方法上定义ExceptionHandler 深入源码分析进入DispatcherServlet执…

axios打通fastapi和vue,实现前后端分类项目开发

axios axios是一个前后端交互的工具&#xff0c;负责在前端代码&#xff0c;调用后端接口&#xff0c;将后端的数据请求到本地以后进行解析&#xff0c;然后传递给前端进行处理。 比如&#xff0c;我们用fastapi写了一个接口&#xff0c;这个接口返回了一条信息&#xff1a; …

环保评A的意义与价值

环保评A&#xff0c;这个看似简单的称谓&#xff0c;背后却蕴藏着深厚的环保理念和实践标准。在当今社会&#xff0c;环保已经成为一项全球性的议题&#xff0c;各国都在努力推动绿色发展&#xff0c;实现可持续发展目标。那么&#xff0c;环保评A究竟是全国性的认证还是地方性…

亿达中国武汉园区入选“武汉市科技金融工作站”及“武汉市线下首贷服务站”

近日&#xff0c;武汉市2024科技金融早春行活动在深交所湖北资本市场培育基地举行。会上&#xff0c;第四批武汉市科技金融工作站试点单位名单及第五批武汉地区金融系统线下首贷服务站名单正式公布&#xff0c;武汉软件新城成功入选上述两个名单。 为缓解科技型企业融资难题&a…

profile-3d-contrib,github三维立体图的使用

图片展示: 提示: 这个profile-3d-contrib存储库有时候会出现问题,导致又有使用这个存储库svg的用户显示出现问题. 参考: https://zhuanlan.zhihu.com/p/681786778 原仓库链接&#xff1a; GitHub - yoshi389111/github-profile-3d-contrib: This GitHub Action creates a Gi…

解决javadoc一直找不到路径的问题

解决javadoc一直找不到路径的问题 出现以上问题就是我们在下载jdk的时候一些运行程序安装在C:\Program Files\Common Files\Oracle\Java\javapath下&#xff1a; 一开始是没有javadoc.exe文件的&#xff0c;我们只需要从jdk的bin目录下找到复制到这个里面&#xff0c;就可以使用…

微信公众号打通与登录的实现

今天实现一下与微信公众号进行对接&#xff0c;通过扫描二维码的方式来进行注册与登录&#xff0c;获取用户的微信唯一标识作为用户的username&#xff0c;下面我们开始编写。 骨架建立&#xff1a; 建包&#xff1a; 第一步还是先将骨架建好&#xff0c;与网关骨架差不多&a…

MEMS:Lecture 16 Gyros

陀螺仪原理 A classic spinning gyroscope measures the rotation rate by utilizing the conservation of angular momentum. 经典旋转陀螺仪通过利用角动量守恒来测量旋转速率。 Coriolis Effect and Coriolis Force 科里奥利效应是一种出现在旋转参考系中的现象。它描述了…

外链建设如何进行?

理解dofollow和nofollow链接&#xff0c;所谓dofollow链接&#xff0c;就是可以传递权重到你的网站的链接&#xff0c;这种链接对你的网站排名非常有帮助&#xff0c;这种链接可以推动你的网站在搜索结果中的位置向上爬&#xff0c;但一个网站全是这种有用的链接&#xff0c;反…

人工智能GPU互联技术分析,芯片巨头UALink向英伟达NVLink开战

芯片巨头组团&#xff0c;向英伟达NVLink开战 八大科技巨头——AMD、博通、思科、Google、惠普企业、英特尔、Meta及微软——联合推出UALink&#xff08;Ultra Accelerator Link&#xff09;技术&#xff0c;为人工智能数据中心网络设定全新互联标准。此举旨在打破Nvidia的市场…

本地GPT-window平台 搭建ChatGLM3-6B

一 ChatGLM-6B 介绍 ChatGLM-6B 是一个开源的、支持中英双语的对话语言模型&#xff0c;新一代开源模型 ChatGLM3-6B 已发布&#xff0c;拥有10B以下最强的基础模型&#xff0c;支持工具调用&#xff08;Function Call&#xff09;、代码执行&#xff08;Code Interpreter&…

面试题 17.06. 2出现的次数

题解&#xff1a;. - 力扣&#xff08;LeetCode&#xff09;. - 力扣&#xff08;LeetCode&#xff09; 数位 DP 通用模板_哔哩哔哩_bilibili class Solution { public:int numberOf2sInRange(int n) {std::string str to_string(n);int len str.size();std::vector<std:…

构建旧物回收系统的决策支持系统

内容概要&#xff1a; 在旧物回收系统中&#xff0c;构建一个有效的决策支持系统对于提高管理效率、优化资源配置具有重要意义。本文将探讨如何构建旧物回收系统的决策支持系统&#xff0c;并分析其如何辅助管理者做出更科学的决策。 一、决策支持系统的定义与功能 决策支持…