背包问题---

一、背包模型

        有一个体积为V的背包,商店有n个物品,每个物品有一个价值v和体积w,每个物品只能被拿一次,问能够装下物品的最大价值。

        这里每一种物品只有两种状态即"拿"或"不拿".

        设状态dp[i][j]表示到第i个物品为止,拿的物品总体积为j的情况下的最大价值。

        并不关心某个物品有没有被拿,只关心当前体积下的最大价值。

        转移方程为:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);如果不拿物品i,那么最大价值就是dp[i-1][j],如果拿了就是从体积j-v转移过来,体积会变大w,价值增加v。

        最后输出dp[n][v];

例题---小明的背包1

https://www.lanqiao.cn/problems/1174/learning/

        小明有一个容量为V的背包。这天他去商场购物,商场一共有N件物品,第i件物品的体积为w_{i},价值为v_{i}

        小明想知道在购买的物品总体积不超过V的情况下所能获得的最大价值为多少,请你帮他算算。

输入描述:输入第1行包含两个正整数N,V,表示商场物品的数量和小明的背包容量。

                  第2~N+1行包含2个正整数w,v,表示物品的体积和价值。

1<=N<=10^{2},1<=V<=10^{3},1<=w_{i},v_{i}<=10^{3}

输出描述:输出一行整数表示小明所能获得的最大价值。

示例:5 20

           1 6

           2 5

           3 8

           5 15

           3 3                                                                                          37

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();// num of things
        int weight = scan.nextInt();// the package weight
        int v[] = new int[n];// value of thing
        int w[] = new int[n];// weight of thing
        int dp[][] = new int[n + 1][weight + 1];
        for (int i = 0; i < n; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < weight + 1; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (j < w[i - 1]) {
                    dp[i][j]=dp[i-1][j];
                }
                else {
                    dp[i][j]=Math.max(dp[i-1][j], v[i-1]+dp[i-1][j-w[i-1]]);
                }
            }
        }
        System.out.println(dp[n][weight]);
        scan.close();
    }
}

2、01背包的优化

例题---背包与魔法

https://www.lanqiao.cn/problems/2223/learning/

        小蓝面前有N件物品,其中第i件重量是w_{i},价值是

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

网络网络层之(3)IPv6地址

网络网络层之(3)IPv6协议 Author: Once Day Date: 2024年4月2日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

简化备案域名查询的最新API接口

随着互联网的发展&#xff0c;越来越多的网站和域名被注册和备案。备案域名查询是一个非常重要的功能&#xff0c;可以帮助用户在特定时间段内查询已备案的域名信息。现在&#xff0c;我将介绍一个简化备案域名查询的最新API接口&#xff0c;该接口可以帮助用户快速查询备案域名…

SQL 注入神器:jSQL Injection 保姆级教程

一、介绍 jSQL Injection是一种用于检测和利用SQL注入漏洞的工具&#xff0c;它专门针对Java应用程序进行SQL注入攻击。以下是关于jSQL Injection的一些介绍&#xff1a; 功能特点&#xff1a; 自动化扫描&#xff1a; jSQL Injection具有自动化扫描功能&#xff0c;能够检测J…

Cesium入门路上的问题解决和知识点集合

想要进行cesium事件处理&#xff0c;必然会涉及到Cesium.ScreenSpaceEventHandler(viewer.scene.canvas)但是与js不同&#xff0c;viewer的位置要先于viewer调用代码大小写错了&#xff0c;就会找不到构造的东西​ 练习时这个方法无效主要是setInputAction方法的括号位置错误应…

精品推荐-2024护网HVV实战教程资料合集(共20章)

以下是资料目录&#xff0c;如需下载&#xff0c;请前往星球获取&#xff1a;https://t.zsxq.com/19vwYrf4t 精品推荐&#xff0c;2024护网HVV实战教程资料合集&#xff0c;压缩包内涵大量实战资料&#xff0c;共20章。星球内会持续更新教程包。 01-HW介绍.zip 02-HTTP&Bu…

揭秘微信如何设置自动回复

01 自动通过好友后自动回复设置 02 个人聊天的关键字自动回复设置 不仅如此&#xff0c;在微信私域管理系统上还可以进行批量多个号自动添加好友、批量群发、定时发朋友圈等操作&#xff0c;可以大幅度提升工作效率&#xff0c;将繁琐的任务交给系统来完成&#xff0c;从而节省…

【【萌新的Pytorch入门之Python的学习】】

学习记录 - 参考记录来自B站up主 -爆肝杰哥 ① NumPy 包为 Python 加上了关键的数组变量类型&#xff0c;弥补了 Python 的不足&#xff1b; ② Pandas 包在 NumPy 数组的基础上添加了与 Excel 类似的行列标签&#xff1b; ③ Matplotlib 库借鉴 Matlab&#xff0c;帮 Python 具…

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读 论文概况Introduction问题一&#xff1a;**现有的节点标记技巧只能帮助感知路径深度&#xff0c;而缺乏对路径“宽度”的感知&#xff0c;例如节点度或路径数量**。问题二&#xff1a;G…

软考117-上午题-【计算机网络】-杂题+小结

一、杂题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 真题6&#xff1a; 真题7&#xff1a; 真题8&#xff1a; 真题9&#xff1a; 真题10&#xff1a; 真题11&#xff1a; 真题12&#xff1a; 真题13&#xff1a; 真题14&a…

【算法集训】基础算法:二分查找 | 概念篇

二分枚举&#xff0c;也叫二分查找&#xff0c;指的就是给定一个区间&#xff0c;每次选择区间的中点&#xff0c;并且判断区间中点是否满足某个条件&#xff0c;从而选择左区间继续求解还是右区间继续求解&#xff0c;直到区间长度不能再切分为止。 由于每次都是把区间折半&am…

AUTOSAR MCAL for SemiDrive E3 功能模块使用介绍:I2C

一、 概述 本文主要介绍如何使用芯驰提供的 AUTOSAR MCAL 软件包&#xff0c;开发 SemiDrive E3 的 I2C 模块&#xff0c;对 RTC 芯片进行读写操作。 硬件使用 E3640 GATEWAY 开发板&#xff0c;软件包为 mcal3.1。 图1 硬件环境 二、模块简介 E3 系列最多支持 8 个 I2C&am…

【51单片机入门记录】A/D D/A转换器概述

目录 一、A/D D/A转换器简介 &#xff08;1&#xff09;模数转换器-ADC &#xff08;analogue-to-digital conversion&#xff09; &#xff08;2&#xff09;数模转换器-DAC&#xff08;digital-to-analogue conversion&#xff09; &#xff08;3&#xff09;应用场景 二…

全国计算机等级考试三级Linux应用与开发技术考试-习题汇总

https://blog.csdn.net/qq_42025798/article/details/119155696 3.第1章-计算机体系结构与操作系统-练习题-简答题 https://blog.csdn.net/qq_42025798/article/details/119186151 4.第1章-计算机体系结构与操作系统-练习题-填空题 https://blog.csdn.net/qq_42025798/article/…

gulp项目配置,压缩css,压缩js,进行监听文件改动

1&#xff0c;创建项目 npm install -g gulp这个应该很熟悉&#xff0c;就是全局安装gulp 2&#xff0c;创建一个工程&#xff0c;使用node创建&#xff0c;统一命令 npm init -y3,创建后&#xff0c;目录出现一个package.json文件&#xff0c;没错&#xff0c;就是我们用vu…

【Leetcode每日一题】模拟 - 外观数列(难度⭐⭐)(51)

1. 题目解析 题目链接&#xff1a;38. 外观数列 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 所谓“外观数列”&#xff0c;其实只是依次统计字符串中连续且相同的字符的个数。依照题意&#xff0c;依次模拟即 可。…

Java面向对象进阶基础知识

面向对象进阶 static 静态变量 被该类的所有的对象共享 不属于对象,属于类 随着类的加载而加载,优先于对象存在 类名调用(推荐) 对象名调用 static的注意事项 静态方法中没有this关键字 静态方法,只能访问静态 非静态方法可以访问所有 在Java中&#xff0c;static关…

元宇宙虚拟空间的碰撞体检测(四)

前言 该文章主要讲元宇宙虚拟空间的碰撞体检测&#xff0c;基本技术点&#xff0c;不多说&#xff0c;直接引入正题。 碰撞体检测 这里可以看到检测代码的逻辑是经过一系列判断&#xff0c;最后判断模型类型属性如果是trimesh&#xff0c;那么通过解析出来的顶点来生成我们的…

Linux:IO多路转接之select

文章目录 selecttimeval结构体fd_set 优缺点分析完整代码 本节要介绍的主题是多路转接式IO select 先说结论&#xff0c;这个select是做什么的呢&#xff1f; select是负责在Linux系统中&#xff0c;让一个人可以有多个鱼竿&#xff0c;可以不停的进行轮询&#xff0c;只要有…

【C语言基础】:文件操作详解(前篇:准备知识)

文章目录 一、什么是文件以及文件的分类1.1 程序文件1.2 数据文件1.3 文件名 二、文本文件和二进制文件2.1 数据在文件中的存储 三、文件的打开和关闭3.1 流和标准流3.1.1 流3.1.2 标准流 3.3 文件指针3.5 文件的打开和关闭 一、什么是文件以及文件的分类 文件是指存储在计算机…