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背包问题暴力解法(回溯法)和经典解法
暴力解法(回溯法) 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考试这几年来虽然版本在升级,但题目一直没有大的变化,通过K8S考试的方法就是在模拟环境上反复练习,通过练习熟悉考试环境和考试过程中可能遇到的坑。这里姚远老师详细向大家介绍一下考试的环境和题目,需要详细资料的同学请在文…...
docker清理
1. 查看docker 磁盘占用 docker system df 2. 参考: Docker磁盘占用与清理问题_docker system prune_蓝鲸123的博客-CSDN博客...
队列和栈两种数据结构的区别和Python实现
队列和栈是两种数据结构,其内部都是按照固定顺序来存放变量的,二者的区别在于对数据的存取顺序 栈是最后存入的数据最先取出,即后进先出 队列是先存入的数据最先取出,即先进先出 Python实现栈 使用append()方法存入数据,使用pop()方法读取数据 # 定义一个空列表(当做栈使…...
java 企业工程管理系统软件源码+Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis
鸿鹄工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离构建工程项目管理系统 1. 项目背景 一、随着公司的快速发展,企业人员和经营规模不断壮大。为了提高工程管理效率、减轻劳动强度、提高信息处理速度和准确性,公司对内部工程管…...
使用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插值(重点)6 三次样条插值(重点)7 各种插值法总结8 n 维数据的插值9 插值法拓展10 课后作业 1 插值法概述 数模比赛中,常常需要根据已知的函数点进…...
rhcsa学习2(vim、创建管理用户、组等)
创建、查看和编辑文本文件 重定向符号 > 进程使用称为文件描述符的编号通道来获取输入并发送输出。所有进程在开始时至少要有三个文件描述符。如果程序打开连接至其他文件的单独连接,则可能要使用更大编号的文件描述符 上述通过通道1去写入,且写入的文…...
【使用教程】Github(自用)
1.下载Git⼯具 使在windows 命令⾏下边可以输⼊这两个命令: gitssh-keygen 2.配置git信息: 在命令⾏⾥输⼊: $ git config --global user.name “你在Github上注册的账号” $ git config --global user.email 你在Github上注册的邮箱 3. c…...
typeScript学习笔记(一)
学习资源来自: 类与接口 TypeScript 入门教程 (xcatliu.com) 一.TypeScript的安装和运行 1.安装TypeScript 通过npm(Node.js包管理器)安装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用户的家目录,要求:不能使用":"作为分割 2.思维导图...
灰度变换与空间滤波
灰度变换与空间滤波 背景知识 空间域指包含图像像素的平面,灰度变换与空间滤波均在空间域进行,即直接在图像像素上操作,表示为 g ( x , y ) T [ f ( x , y ) ] g(x,y)T[f(x,y)] g(x,y)T[f(x,y)] ,其中 T T T 是在点 ( x , y…...
敏感接口权限校验
前端校验 (从前端或者从token里面拿一下),看一下用户有没有这个页面的权限(但是一般不用,因为nodejs也可以写后端,但是放到前端去校验不安全) 后端校验 需要梳理敏感数据接口,将这…...
[LeetCode周赛复盘] 第 112场双周赛20230903
[LeetCode周赛复盘] 第 112场双周赛20230903 一、本周周赛总结2839. 判断通过操作能否让字符串相等 I1. 题目描述2. 思路分析3. 代码实现 2840. 判断通过操作能否让字符串相等 II1. 题目描述2. 思路分析3. 代码实现 2841. 几乎唯一子数组的最大和1. 题目描述2. 思路分析3. 代码…...
Spark【RDD编程(二)RDD编程基础】
前言 接上午的那一篇,下午我们学习剩下的RDD编程,RDD操作中的剩下的转换操作和行动操作,最好把剩下的RDD编程都学完。 Spark【RDD编程(一)RDD编程基础】 RDD 转换操作 6、distinct 对 RDD 集合内部的元素进行去重…...
【2023最新版】MySQL安装教程
目录 一、MySQL简介 二、MySQL安装 1. 官网 2. 下载 3. 安装 4. 配置环境变量 配置前 配置中 配置后 5. 验证 一、MySQL简介 MySQL是一种开源的关系型数据库管理系统(RDBMS),它被广泛用于存储和管理结构化数据。MySQL提供了强大的功…...
关于mysql数据文件损坏导致的mysql无法启动的问题
环境 rocky linux 9 (跟centos几乎一模一样) myqsl 8.0, 存储引擎使用innodb 问题描述 1. 服务器异常关机,重启启动后发现mysql无法连接,使用命令查看mysql状态: systemctl status mysqld 发现mysql服…...
深度学习之视频分类项目小记
写在前面,最近一阵在做视频分类相关的工作,趁有时间来记录一下。本文更注重项目实战与落地,而非重点探讨多模/视频模型结构的魔改 零、背景 目标:通过多模态内容理解技术,构建视频层级分类体系原技术方案:…...
pandas(四十三)Pandas实现复杂Excel的转置合并
一、Pandas实现复杂Excel的转置合并 读取并筛选第一张表 df1 pd.read_excel("第一个表.xlsx") df1# 删除无用列 df1 df1[[股票代码, 高数, 实际2]].copy() df1df1.dtypes股票代码 int64 高数 float64 实际2 int64 dtype: object读取并处理第二张表…...
Tencent Hunyuan3D-1.0学术合作机会:腾讯混元团队的研究方向与合作模式
Tencent Hunyuan3D-1.0学术合作机会:腾讯混元团队的研究方向与合作模式 【免费下载链接】Hunyuan3D-1 腾讯开源的Hunyuan3D-1项目,创新提出两阶段3D生成方法,实现快速、高质量的文本到3D和图像到3D转换,融合Hunyuan-DiT模型&#…...
Pixel Epic动态卷轴效果展示:从空白屏幕到完整研报的实时生成录屏
Pixel Epic动态卷轴效果展示:从空白屏幕到完整研报的实时生成录屏 1. 引言:当科研遇上像素冒险 在传统的研究报告撰写过程中,我们常常面对冰冷的界面和机械化的交互体验。Pixel Epic彻底改变了这一现状,将严肃的学术研究变成了一…...
告别手速焦虑:Python大麦网自动抢票脚本终极指南
告别手速焦虑:Python大麦网自动抢票脚本终极指南 【免费下载链接】Automatic_ticket_purchase 大麦网抢票脚本 项目地址: https://gitcode.com/GitHub_Trending/au/Automatic_ticket_purchase 还在为心仪演出门票秒光而烦恼吗?每次热门演唱会开票…...
显卡驱动彻底清理指南:用DDU解决90%的显示问题
显卡驱动彻底清理指南:用DDU解决90%的显示问题 【免费下载链接】display-drivers-uninstaller Display Driver Uninstaller (DDU) a driver removal utility / cleaner utility 项目地址: https://gitcode.com/gh_mirrors/di/display-drivers-uninstaller 当…...
解密Wallpaper Engine资源宝库:RePKG工具完全实战指南
解密Wallpaper Engine资源宝库:RePKG工具完全实战指南 【免费下载链接】repkg Wallpaper engine PKG extractor/TEX to image converter 项目地址: https://gitcode.com/gh_mirrors/re/repkg RePKG是一款专为Wallpaper Engine设计的开源资源处理工具…...
技术Lead:不亲手解决问题,你的位置还稳吗?
做到技术Lead这个位置,很多人开始纠结一件事——到底该不该自己动手?技术Lead的尴尬,其实很具体比如前端设计阶段,团队在讨论一个时序收敛问题,工程师说某条路径的slack是-0.3ns,建议加pipeline。这时候Lea…...
手把手教你将自定义视频问答JSON转成EasyR1可用的Parquet数据集
手把手教你将自定义视频问答JSON转成EasyR1可用的Parquet数据集 当你在构建视频问答模型时,可能已经收集了大量结构化的JSON格式数据,但如何将这些数据适配到EasyR1框架中却成了一个技术难题。本文将为你提供一个从零开始的完整解决方案,解决…...
Z-Image Atelier 生成动态效果预览:通过序列图像模拟简单动画过程
Z-Image Atelier 生成动态效果预览:通过序列图像模拟简单动画过程 最近在玩一个挺有意思的AI图像工具,叫Z-Image Atelier。它最吸引我的地方,不是生成单张多么精美的图片,而是它能帮你“脑补”出一段动态过程。简单来说ÿ…...
Ubuntu 22.04 改IP重启失效?别急,可能是OVS的ovsdb-server在捣鬼
Ubuntu 22.04网络配置失效:当OVS与netplan的隐秘博弈 在虚拟化技术大行其道的今天,Open vSwitch(OVS)作为开源虚拟交换机的标杆,已经成为众多云计算平台和容器网络的核心组件。然而,当它遇上Ubuntu 22.04默…...
从HuggingFace下载到本地部署:手把手教你定制自己的BertTokenizer工作流
从HuggingFace下载到本地部署:手把手教你定制自己的BertTokenizer工作流 在自然语言处理项目中,一个高效且灵活的分词器往往是整个流程的基石。BertTokenizer作为HuggingFace生态中的核心组件,其预训练版本能够处理绝大多数英文和中文文本处理…...
