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

01背包问题暴力解法(回溯法)和经典解法

暴力解法(回溯法)

import java.util.Arrays;
import java.util.Scanner;public class Main {private final static int  N = 999;public static int SumValue = 0;public static int SumWeight = 0;public static int OptimalValue = 0;public static int OptimalSolution[] = new int[N];public static int w[] = new int[N];public static int v[] = new int[N];public static int x[] = new int[N];public static int n;public static int c;public static void  backTracking(int t) {if(t>n) {if(SumValue > OptimalValue) {OptimalValue = SumValue;for(int i=1;i<=n;i++)OptimalSolution[i]=x[i];}}else {for(int i=0;i<=1;i++) {x[t]=i;if(i==0) {backTracking(t+1);}else {if(SumValue+w[t]<=c) {SumWeight += w[t];SumValue += v[t];backTracking(t+1);SumValue -= v[t];SumWeight -= w[t];}}}}}public static void main(String[] args) {// TODO Auto-generated method stubScanner sc =new Scanner(System.in);n = sc.nextInt();Arrays.fill(w, 0);Arrays.fill(v, 0);Arrays.fill(x, 0);c = sc.nextInt();for(int i=1;i<=n;i++){int temp = sc.nextInt();w[i]=temp;temp = sc.nextInt();v[i]=temp;}backTracking(1);System.out.print(OptimalValue);}}

二维数组(经典解法) 这里dp[i][j]表示含义是取[0,i]个物品且容量不超过j的最大价值为dp[i][j]

import java.nio.file.Watchable;
import java.util.Scanner;public class 经典解法Test {public static void main(String[] args) {int n;int N = 999;int[][] dp =new int[N][N];Scanner scanner=new Scanner(System.in);n=scanner.nextInt();int c;c=scanner.nextInt();int[] w=new int[N];int[] v = new int[N];for(int i=0;i<n;i++) {int temp=scanner.nextInt();w[i]=temp;temp=scanner.nextInt();v[i]=temp;}for(int i=0;i<n;i++)dp[i][0]=0;for(int i=w[0];i<=c;i++)dp[0][i]=v[0];for(int i=1;i<n;i++) {for(int j=c;j>=0;j--) {if(j>=w[i]) {dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);}else {dp[i][j]=dp[i-1][j];}}}System.out.println(dp[n-1][c]);}
}

一维数组(经典解法)dp[j] 含义是容量不超过j且最大价值为dp[j]

import java.util.Scanner;public class 一维数组 {public static void main(String[] args) {int N=999;int n,c;int[] w= new int[N];int[] v=new int[N];int[] dp=new int[N];Scanner scanner=new Scanner(System.in);n=scanner.nextInt();c=scanner.nextInt();for(int i=0;i<n;i++) {int temp=scanner.nextInt();w[i]=temp;temp=scanner.nextInt();v[i]=temp;}dp[0]=0;for(int i=0;i<n;i++) {for(int j=c;j>=w[i];j--)dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);}System.out.println(dp[c]);}
}

相关文章:

01背包问题暴力解法(回溯法)和经典解法

暴力解法&#xff08;回溯法&#xff09; import java.util.Arrays; import java.util.Scanner;public class Main {private final static int N 999;public static int SumValue 0;public static int SumWeight 0;public static int OptimalValue 0;public static int O…...

K8S的CKA考试环境和题目

CKA考试这几年来虽然版本在升级&#xff0c;但题目一直没有大的变化&#xff0c;通过K8S考试的方法就是在模拟环境上反复练习&#xff0c;通过练习熟悉考试环境和考试过程中可能遇到的坑。这里姚远老师详细向大家介绍一下考试的环境和题目&#xff0c;需要详细资料的同学请在文…...

docker清理

1. 查看docker 磁盘占用 docker system df 2. 参考&#xff1a; Docker磁盘占用与清理问题_docker system prune_蓝鲸123的博客-CSDN博客...

队列和栈两种数据结构的区别和Python实现

队列和栈是两种数据结构,其内部都是按照固定顺序来存放变量的,二者的区别在于对数据的存取顺序 栈是最后存入的数据最先取出,即后进先出 队列是先存入的数据最先取出,即先进先出 Python实现栈 使用append()方法存入数据,使用pop()方法读取数据 # 定义一个空列表(当做栈使…...

java 企业工程管理系统软件源码+Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis

鸿鹄工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离构建工程项目管理系统 1. 项目背景 一、随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大。为了提高工程管理效率、减轻劳动强度、提高信息处理速度和准确性&#xff0c;公司对内部工程管…...

使用Smartctl脚本输入当前所有磁盘的状态

一、安装Smartctl yum install smartmontools 二、写一个脚本输出当前所有磁盘的状态并且按名称分别写入到文件中 #!/bin/bashfor dev in $(lsblk -l | grep disk | awk {print $1}) doecho "检测磁盘 $dev"smartctl -a /dev/$dev > $dev.smartctl done 以下是这…...

数学建模之插值法

目录 1 插值法概述2 插值法原理3 拉格朗日插值4 牛顿插值5 三次Hermite插值&#xff08;重点&#xff09;6 三次样条插值&#xff08;重点&#xff09;7 各种插值法总结8 n 维数据的插值9 插值法拓展10 课后作业 1 插值法概述 数模比赛中&#xff0c;常常需要根据已知的函数点进…...

rhcsa学习2(vim、创建管理用户、组等)

创建、查看和编辑文本文件 重定向符号 > 进程使用称为文件描述符的编号通道来获取输入并发送输出。所有进程在开始时至少要有三个文件描述符。如果程序打开连接至其他文件的单独连接&#xff0c;则可能要使用更大编号的文件描述符 上述通过通道1去写入&#xff0c;且写入的文…...

【使用教程】Github(自用)

1.下载Git⼯具 使在windows 命令⾏下边可以输⼊这两个命令&#xff1a; gitssh-keygen 2.配置git信息&#xff1a; 在命令⾏⾥输⼊&#xff1a; $ git config --global user.name “你在Github上注册的账号” $ git config --global user.email 你在Github上注册的邮箱 3. c…...

typeScript学习笔记(一)

学习资源来自&#xff1a; 类与接口 TypeScript 入门教程 (xcatliu.com) 一.TypeScript的安装和运行 1.安装TypeScript 通过npm&#xff08;Node.js包管理器&#xff09;安装Visual Studio的TypeScript插件:(Visual Studio 2017和Visual Studio 2015 Update 3默认包含了Ty…...

第4章:网络层

文章目录 一、概述和功能2.SDN二、转发1.IP数据报(1)IP数据报的首部字段(2)IP数据报的分片2.IPv4地址:<网络号>,<主机号>3.IP编址 (三个历史阶段)(1)分类IP地址①特殊IP地址②私有IP地址③网络地址转换NAT:导致IP地址变化MAC地址、IP地址变化问题(2)子网划分与子…...

C高级day1 shell 指令的补充学习

使用cut截取出Ubuntu用户的家目录&#xff0c;要求&#xff1a;不能使用":"作为分割 2.思维导图...

灰度变换与空间滤波

灰度变换与空间滤波 背景知识 空间域指包含图像像素的平面&#xff0c;灰度变换与空间滤波均在空间域进行&#xff0c;即直接在图像像素上操作&#xff0c;表示为 g ( x , y ) T [ f ( x , y ) ] g(x,y)T[f(x,y)] g(x,y)T[f(x,y)] &#xff0c;其中 T T T 是在点 ( x , y…...

敏感接口权限校验

前端校验 &#xff08;从前端或者从token里面拿一下&#xff09;&#xff0c;看一下用户有没有这个页面的权限&#xff08;但是一般不用&#xff0c;因为nodejs也可以写后端&#xff0c;但是放到前端去校验不安全&#xff09; 后端校验 需要梳理敏感数据接口&#xff0c;将这…...

[LeetCode周赛复盘] 第 112场双周赛20230903

[LeetCode周赛复盘] 第 112场双周赛20230903 一、本周周赛总结2839. 判断通过操作能否让字符串相等 I1. 题目描述2. 思路分析3. 代码实现 2840. 判断通过操作能否让字符串相等 II1. 题目描述2. 思路分析3. 代码实现 2841. 几乎唯一子数组的最大和1. 题目描述2. 思路分析3. 代码…...

Spark【RDD编程(二)RDD编程基础】

前言 接上午的那一篇&#xff0c;下午我们学习剩下的RDD编程&#xff0c;RDD操作中的剩下的转换操作和行动操作&#xff0c;最好把剩下的RDD编程都学完。 Spark【RDD编程&#xff08;一&#xff09;RDD编程基础】 RDD 转换操作 6、distinct 对 RDD 集合内部的元素进行去重…...

【2023最新版】MySQL安装教程

目录 一、MySQL简介 二、MySQL安装 1. 官网 2. 下载 3. 安装 4. 配置环境变量 配置前 配置中 配置后 5. 验证 一、MySQL简介 MySQL是一种开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它被广泛用于存储和管理结构化数据。MySQL提供了强大的功…...

关于mysql数据文件损坏导致的mysql无法启动的问题

环境 rocky linux 9 &#xff08;跟centos几乎一模一样&#xff09; myqsl 8.0&#xff0c; 存储引擎使用innodb 问题描述 1. 服务器异常关机&#xff0c;重启启动后发现mysql无法连接&#xff0c;使用命令查看mysql状态&#xff1a; systemctl status mysqld 发现mysql服…...

深度学习之视频分类项目小记

写在前面&#xff0c;最近一阵在做视频分类相关的工作&#xff0c;趁有时间来记录一下。本文更注重项目实战与落地&#xff0c;而非重点探讨多模/视频模型结构的魔改 零、背景 目标&#xff1a;通过多模态内容理解技术&#xff0c;构建视频层级分类体系原技术方案&#xff1a…...

pandas(四十三)Pandas实现复杂Excel的转置合并

一、Pandas实现复杂Excel的转置合并 读取并筛选第一张表 df1 pd.read_excel("第一个表.xlsx") df1# 删除无用列 df1 df1[[股票代码, 高数, 实际2]].copy() df1df1.dtypes股票代码 int64 高数 float64 实际2 int64 dtype: object读取并处理第二张表…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...