0-1背包的初始化问题
题目链接
这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下,容量为j时能放物品的数量(这道题歌曲数量对应物品数量,容量对应时间)。
技巧(收获)
-
二维dp数组可以视情况优化为一维dp数组。
-
在0-1背包问题的初始化中
背包必须装满,dp[0] = 0,其他初始化为负无穷背包可以不装满,dp全部初始化为0,有关这一点的解释。 -
在遍历时,如果是找价值最大的,从后往前遍历。

参考:https://blog.csdn.net/pegasuswang_/article/details/9131619
#include <stdio.h>
#define jinge 678int max(int a, int b) {return a > b ? a : b;
}int main() {int T, n, t;int i, j; scanf("%d", &T);int song[51] = {0};int dp[10000] = {0};int count = 1;while (T--) {scanf("%d %d", &n, &t);for (i = 1; i <= n; i++) {scanf("%d", &song[i]);}for (i = 0; i <= t; i++) { dp[i] = -1;}dp[0] = 0;int ans = 0,ans_time = 0;for (i = 1; i <= n; i++) {for (j = t-1; j >= song[i]; j--) {if(dp[j - song[i]] + 1>=dp[j]){dp[j] = dp[j - song[i]] + 1;//这里的dp[j] = dp[j - song[i]] + 1;相当于dp[i][j] = dp[i-1][j - song[i]] + 1;}}}for(j=t-1;j>0;j--)if(dp[j]>ans){ans = dp[j];ans_time = j;}for(int i=0;i<t;i++){printf("%3d ",dp[i]);}printf("Case %d: %d %d\n", count++, ans + 1, ans_time + jinge);}return 0;
}/*
2
3 100
60 70 80
3 100
30 69 70
*/
相关文章:
0-1背包的初始化问题
题目链接 这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下,容量为j时能放物品的数量(这道题歌曲数量对应物品数量,容量对应时间)。 技巧(收获) 二维dp数组可以视情况优化为一维dp数组…...
API之 要求接口上传pdf 以 合同PDF的二进制数据,multpart方式上传
实现 //时间戳13位毫秒private function getMillisecond() {list($s1,$s2) explode( ,microtime());return (float)sprintf(%.0f,(floatval($s1) floatval($s2)) * 1000);}// 组装参数private function gysscPost1($url,$data){// $data[timestamp] 1694402111964;$data[tim…...
C语言-求阶乘序列前N项和
本题要求编写程序,计算序列 1!2!3!⋯ 的前N项之和。 输入格式: 输入在一行中给出一个不超过12的正整数N。 输出格式: 在一行中输出整数结果。 输入样例: 5输出样例: 153 #include "stdio.h" int main(){int n;int sum 0;scanf("%d",&a…...
3:kotlin 逻辑控制(Control flow)
像其他语言一样,kotlin也有循环和逻辑控制 条件判断(Conditional expressions) kotlin使用if和when来进行条件判断 如果纠结选择if还是when,建议使用when,因为它更能提高程序的健壮性 if 普通写法 fun main() {val…...
Linux系统之一次性计划任务at命令的基本使用
Linux系统之一次性计划任务at命令的基本使用 一、at命令介绍二、at命令的使用帮助2.1 at命令的help帮助信息2.2 at命令的语法解释 三、at命令的日常使用3.1 立即执行一次性任务3.2 指定时间执行一次性任务3.3 查询计划任务3.4 其他指定时间用法3.5 删除已经设置的计划任务3.6 显…...
记录:Unity脚本的编写8.0
目录 需求分析设计GUI包含账号和密码输入栏,包括登录和注册按键添加背景音乐编写脚本控制音乐 退出按钮编写脚本 背景图片完整代码 一个小demo,登录和注册的实现(包括GUI和数据库操控) 需求分析 自行设计GUI,要求 1.包…...
OpenCV | 模版匹配
import cv2 #opencv读取的格式是BGR import numpy as np import matplotlib.pyplot as plt#Matplotlib是RGB %matplotlib inline 模版匹配 模版匹配和卷积原理很像,模版在原图像上从原点开始滑动,计算模版与(图像被模版覆盖的地方ÿ…...
【算法刷题】Day7
文章目录 283. 移动零1089. 复写零 283. 移动零 原题链接 看到题目,首先看一下题干的要求,是在原数组内进行操作,平切保持非零元素的相对顺序 这个时候我们看到了示例一: [ 0, 1, 0, 3,12 ] 这个时候输出成为了 [ 1, 3, 12, 0, …...
前端 | iframe框架标签应用
文章目录 📚嵌入方式📚图表加载显示📚100%嵌入及滑动条问题📚加载动画保留 前情提要: 计划用iframe把画好的home1.html(echarts各种图表组成的html数据大屏)嵌入整合到index.html(搭…...
linux -系统通用命令查询
有时候内网环境下,系统有些命令没有安装因此掌握一些通用的linux 命令也可以帮助我们解决一些问题查看 1.查看系统内核版本 uname -r2.查看系统版本 cat /etc/os-release3. 查看cpu 配置 lscpu4.查看内存信息 free [参数] 中各个数值的解释如下表 数值解释t…...
python炒股自动化(1),量化交易接口区别
要实现股票量化程序化自动化,就需要券商提供的API接口,重点是个人账户小散户可以申请开通,上手要简单,接口要足够全面,功能完善,首先,第一步就是要找对渠道和方法,这里我们不讨论量化…...
LeetCode(35)螺旋矩阵【矩阵】【中等】
目录 1.题目2.答案3.提交结果截图 链接: 54. 螺旋矩阵 1.题目 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix [[1,2,3],[4,5,6],[7,8,9]] 输出:…...
BeanUtil.copyProperties的优化与使用(解决copyProperties null值覆盖问题)
BeanUtil.copyProperties的优化与使用 前言一、copyProperties是什么?二、使用步骤1.引入库2.基础使用3.进阶使用4.实用场景 总结 前言 BeanUtil.copyProperties的优化与使用 一、copyProperties是什么? 在java中,我们想要将一个类的值赋值…...
Redis基本操作及使用
📑前言 本文主要是【Redis】——Redis基本操作及使用的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一…...
python 继承父类的变量和方法
[root@zz python]# cat a1.py # !/usr/bin/env python # -*- coding: utf-8 -*- class AddrBookEntry(object): ##类定义 def __init__(self,a,b): ##定义构造器 self.var1=a+9 self.var2=b+11 def updatePhone(self, num): # 定义方法 sel…...
ubuntu22.04新机使用(换源,下载软件,安装显卡驱动,锁屏长亮)
换源 国内有很多Ubuntu的镜像源,包括阿里的、网易的,还有很多教育网的源,比如:清华源、中科大源。推荐使用中科大源,快得很。 /etc/apt/sources.list编辑/etc/apt/sources.list文件, 在文件最前面添加以下条目(操作前…...
如何给shopify的网址做301跳转
很多shopify的运营者或者推广者由于缺货或者货物变更,又或者自己更换了使用的主题,导致自己的URL结构发生了变化,由于不想浪费掉自己原有URL 的流量,就想做个301跳转,让自己新的网址来承接原有的流量。接下来给大家介绍…...
Redis之秒杀系统
目录 Redis 秒杀 Mysql数据库设计 Mysql秒杀实现 MysqlRedis秒杀实现 秒杀是一种高并发场景,通常指的是在短时间内(秒级别)有大量用户同时访问某个商品或服务,争相抢购的情景。在这种情况下,系统需要处理大量并发请…...
c++基础----new
c基础----new 在C中,new是一个运算符,用于动态分配内存并返回指向该内存的指针。它可以用于创建单个对象、数组以及动态分配的对象。 下面是new的几种常见用法: 动态分配单个对象: int* ptr new int; // 动态分配一个int类型…...
Java中的mysql——面试题+答案(存储过程,外键,隔离级别,性能优化)——第23期
当涉及MySQL时,面试题的范围可以涵盖数据库设计、优化、复制、分片等方面。 什么是数据库范式?为什么要遵循数据库范式? 答案: 数据库范式是一组规范,用于设计关系数据库表的结构,以减少数据冗余和提高数据…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
