蓝桥杯每日一题------背包问题(三)

前言

之前求的是在特点情况下选择一些物品让其价值最大,这里求的是方案数以及具体的方案。

背包问题求方案数

在这里插入图片描述
既然要求方案数,那么就需要一个新的数组来记录方案数。动态规划步骤如下,
定义dp数组
第一步:缩小规模。考虑n个物品,那我就先考虑1个物品,在考虑2个物品…,需要一个维度表示当前考虑的物品个数。
第二步:限制。所选物品个数不能超过物品容量,那么需要一个维度记录当前背包的容量。
第三步:写出dp数组。f[i][j]表示当前考虑了前i个物品,背包容量为j价值最大时的方案数。
第四步:推状态转移方程。f[i][j]应该从哪里转移过来呢,必然是从前i-1个物品转移,我要考虑两种情况,对于第i个物品,可以选择要它,也可以不要它。
(1)如果要第i个物品,f[i][j]=f[i-1][j-v[i]]。
(2)如果不要第i个物品,f[i][j]=f[i-1][j]。
(3)如果要和不要都可以获得最大价值,f[i][j]=f[i-1][j-v[i]]+f[i-1][j]。
那么在原先的dp数组进行转移的时候,我们要记录他到底是从哪个状态转移过来的,不能只单纯取一个最大值。代码如下。

int l = dp[j];int r = dp[j-v[i]] + w[i];dp[j] = Math.max(l, r);if(l > r) {f[j] = f[j];}else if (l < r) {f[j] = f[j-v[i]];}else{f[j] = f[j] + f[j-v[i]];}

同时要注意f数组的初始化,当考虑前0个物品时,方案是啥也不选,所以方案数是1,初始化代码如下,

for(int i = 0;i < k+1;i++){f[i] = 1;}

完整代码如下,

import java.util.Scanner;
public class Main {
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();int v[] = new int[n+1];int w[] = new int[n+1];int dp[] = new int[k+1];int f[] = new int[k+1];for (int i = 1; i < n+1; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}for(int i = 0;i < k+1;i++) f[i] = 1;int mod = 1000000007;for (int i = 1; i < n+1; i++) {for (int j = k; j >= v[i]; j--) {int l = dp[j];int r = dp[j-v[i]] + w[i];dp[j] = Math.max(l, r);if(l > r) {f[j] = f[j];}else if (l < r) {f[j] = f[j-v[i]];}else{f[j] = f[j] + f[j-v[i]];}f[j] %= mod;}}System.out.println(f[k]);
}
}

背包问题求具体方案

在这里插入图片描述
正常求dp数组,求完后逆序推回去就行,对于dp[n][m],如果dp[n][m]=dp[n][m-v[i]]+w[i],那么第i个物品被选择,然后再接着往后求dp[n][m-v[i]]。
那么如何保证字典序最小?回顾一下求dp数组的过程,我们是优先考虑的字典序小的物品,但是最后求的时候我们是倒序推导,这样反而字典序大的物品会优先被输出,所以更改一下字典序小的物品放在后面求。
全部代码如下,

import java.util.Scanner;
public class Main {
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int V = scanner.nextInt();int[] v = new int[n+1];int[] w = new int[n+1];for (int i = 1; i < w.length; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}int[][] dp = new int[n+2][V+1];for (int i = n; i > 0; i--) {for (int j = 0; j < V+1; j++) {dp[i][j] = dp[i+1][j];if(v[i] <= j) {dp[i][j] = Math.max(dp[i][j], dp[i+1][j-v[i]] + w[i]);}}}int vv = V;for (int i = 1; i < n+1&&vv>0; i++) {if(vv >= v[i] && dp[i][vv] == dp[i+1][vv-v[i]] + w[i]) {System.out.print(i + " ");vv -= v[i];}}
}
}

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

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

相关文章

云原生容器化-4 Docker仓库

1.Docker仓库 1.1 Docker Hub docker仓库用于存放docker镜像&#xff0c;可以分为公用和私有两种。Docker Hub是全球公用的仓库&#xff0c;因服务器在国外&#xff0c;国内基本不可以&#xff1b;一般需要配置阿里、腾讯等加速器。公司内部而言&#xff0c;可以搭建私有的Do…

使用 devc++ 开发 easyx 实现 Direct2D 交互

代码为 codebus 另一先生的 文案 EasyX 的三种绘图抗锯齿方法 - CodeBus 这里移植到 devc 移植操作如下&#xff1a; 调用dev 的链接库方式&#xff1a; project -> project option -> 如图所示 稍作修改的代码。 #include <graphics.h> #include <d2d1.…

【数据结构】13:表达式转换(中缀表达式转成后缀表达式)

思想&#xff1a; 从头到尾依次读取中缀表达式里的每个对象&#xff0c;对不同对象按照不同的情况处理。 如果遇到空格&#xff0c;跳过如果遇到运算数字&#xff0c;直接输出如果遇到左括号&#xff0c;压栈如果遇到右括号&#xff0c;表示括号里的中缀表达式已经扫描完毕&a…

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(2)折线图显示

对上一篇的工作C学习笔记 | 基于Qt框架开发实时成绩显示排序系统1-CSDN博客继续优化&#xff0c;增加一个显示运动员每组成绩的折线图。 1&#xff09;在Qt Creator的项目文件&#xff08;.pro文件&#xff09;中添加对Qt Charts模块的支持&#xff1a; QT charts 2&#xf…

STM32WLE5JC

Sub-GHz 无线电介绍 sub-GHz无线电是一种超低功耗sub-GHz无线电&#xff0c;工作在150-960MHz ISM频段。 在发送和接收中采用LoRa和&#xff08;G&#xff09;FSK调制&#xff0c;仅在发送中采用BPSK/(G)MSK调制&#xff0c;可以在距离、数据速率和功耗之间实现最佳权衡。 这…

微软 CMU - Tag-LLM:将通用大语言模型改用于专业领域

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 论文地址&#xff1a;https://arxiv.org/abs/2402.05140 Github 地址&#xff1a;https://github.com/sjunhongshen/Tag-LLM 大语言模型&#xff08…

Ubuntu Desktop - scrolling (Terminal 缓存更多终端历史输出内容)

Ubuntu Desktop - scrolling [Terminal 缓存更多终端历史输出内容] 1. ubuntu-14.04.5-desktop-amd64.iso2. ubuntu-16.04.3-desktop-amd64.isoReferences Terminal -> 右键 Profiles -> Profile Preferences 1. ubuntu-14.04.5-desktop-amd64.iso 2. ubuntu-16.04.3-de…

理解JAVA命名和目录接口(JNDI)

理解JAVA命名和目录接口(JNDI) 考虑访问网站的场景,Web用户要求记住四字节的IP地址而不是有意义的名称。例如,假设Web用户用123.23.3.123而不是hotmail.com访问hotmail网站。在这种情形下,Web用户难以记住不同的IP地址来访问不同的网站。因此,要使其变得对Web用户简单方…

【开源】SpringBoot框架开发APK检测管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 开放平台模块2.3 软件档案模块2.4 软件检测模块2.5 软件举报模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 开放平台表3.2.2 软件档案表3.2.3 软件检测表3.2.4 软件举报表 四、系统展示五、核心代…

基于RBF神经网络的自适应控制器simulink建模与仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1自适应控制器 4.2 RBF神经网络模型 5.完整程序 1.程序功能描述 在simulink中&#xff0c;使用S函数编写基于RBF神经网络的自适应控制器&#xff0c;然后实现基于RBF神经网络的自适应控制…

HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-任务管理

目录 一、任务管理1.1、任务状态1.2、任务基本概念1.3、任务管理使用说明1.4、任务开发流程1.5、任务管理接口 坚持就有收获 一、任务管理 从系统角度看&#xff0c;任务是竞争系统资源的最小运行单元。任务可以使用或等待CPU、使用内存空间等系统资源&#xff0c;并独立于其它…

【多模态】27、Vary | 通过扩充图像词汇来提升多模态模型在细粒度感知任务(OCR等)上的效果

文章目录 一、背景二、方法2.1 生成 new vision vocabulary2.1.1 new vocabulary network2.1.2 Data engine in the generating phrase2.1.3 输入的格式 2.2 扩大 vision vocabulary2.2.1 Vary-base 的结构2.2.2 Data engine2.2.3 对话格式 三、效果3.1 数据集3.2 图像细粒度感…

双场板功率GaN HEMT电容模型以精确模拟开关行为

标题&#xff1a;Capacitance Modeling in Dual Field-Plate Power GaN HEMT for Accurate Switching Behavior&#xff08;TED.16年&#xff09; 摘要 本文提出了一种基于表面电位的紧凑模型&#xff0c;用于模拟具有栅极和源极场板&#xff08;FP&#xff09;结构的AlGaN/G…

【Python网络编程之Ping命令的实现】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;Python开发技术 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Python网络编程之Ping命令的实现 代码见资源&#xff0c;效果图如下一、实验要求二、协议原理2…

redis-sentinel(哨兵模式)

目录 1、哨兵简介:Redis Sentinel 2、作用 3、工作模式 4、主观下线和客观下线 5、配置哨兵模式 希望能够帮助到大家&#xff01;&#xff01;&#xff01; 1、哨兵简介:Redis Sentinel Sentinel(哨兵)是用于监控redis集群中Master状态的工具&#xff0c;其已经被集成在re…

问山海——天涯海角——桃花渊boss攻击顺序

文章目录 桃花渊代码代码解读代码执行结果攻击顺序示意图 桃花渊 规划击杀各个boss顺序。 副本持续时间为30分钟&#xff0c;每个地方的boss被打死后&#xff0c;需要一定时间才能重新刷新。 只考虑其中两种boss&#xff0c;龟将和龟龙。各有四个。 其中我从一个boss地点到…

CentOS 7.9安装Tesla M4驱动、CUDA和cuDNN

正文共&#xff1a;1333 字 21 图&#xff0c;预估阅读时间&#xff1a;2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境&#xff08;TensorFlow识别GPU难道就这么难吗&#xff1f;还是我的GPU有问题&#xff1f;&#xff09;&#xff0c;但是失败了。考虑到Windows…

力扣_字符串6—最小覆盖字串

题目 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空字符串 “” 。 示例 &#xff1a; 输入&#xff1a;s “ADOBECODEBANC”, t “ABC” 输出&#xff1a;“BANC” 解释&#xff1a;…

jvm几个常见面试题整理

1. Full GC触发机制有如下5种情况。 (1)调用System.gc()时&#xff0c;系统建议执行Full GC&#xff0c;但是不必然执行。(2)老年代空间不足。(3)方法区空间不足。(4)老年代的最大可用连续空间小于历次晋升到老年代对象的平均大小就会进行Full GC。(5)由Eden区、S0(From)区向S…

【GO语言卵细胞级别教程】05.项目创建和函数讲解

感谢&#xff01;点点赞和评论呀&#xff01;我将继续更新 目录&#xff1a; 感谢&#xff01;点点赞和评论呀&#xff01;我将继续更新0.创建项目1.函数的引入2.注意事项3.详细介绍3.1 形参介绍 4.导入包4.1 基本知识4.2 注意事项 5.init函数6.匿名函数 0.创建项目 创建目录 …