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

0-1背包的初始化问题

题目链接
这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下,容量为j时能放物品的数量(这道题歌曲数量对应物品数量,容量对应时间)。
技巧(收获)

  1. 二维dp数组可以视情况优化为一维dp数组。

  2. 在0-1背包问题的初始化中

    	背包必须装满,dp[0] = 0,其他初始化为负无穷背包可以不装满,dp全部初始化为0,有关这一点的解释。
    
  3. 在遍历时,如果是找价值最大的,从后往前遍历。

在这里插入图片描述
参考: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个物品的情况下&#xff0c;容量为j时能放物品的数量&#xff08;这道题歌曲数量对应物品数量&#xff0c;容量对应时间&#xff09;。 技巧&#xff08;收获&#xff09; 二维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项和

本题要求编写程序&#xff0c;计算序列 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)

像其他语言一样&#xff0c;kotlin也有循环和逻辑控制 条件判断&#xff08;Conditional expressions&#xff09; kotlin使用if和when来进行条件判断 如果纠结选择if还是when&#xff0c;建议使用when&#xff0c;因为它更能提高程序的健壮性 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包含账号和密码输入栏&#xff0c;包括登录和注册按键添加背景音乐编写脚本控制音乐 退出按钮编写脚本 背景图片完整代码 一个小demo&#xff0c;登录和注册的实现&#xff08;包括GUI和数据库操控&#xff09; 需求分析 自行设计GUI&#xff0c;要求 1.包…...

OpenCV | 模版匹配

import cv2 #opencv读取的格式是BGR import numpy as np import matplotlib.pyplot as plt#Matplotlib是RGB %matplotlib inline 模版匹配 模版匹配和卷积原理很像&#xff0c;模版在原图像上从原点开始滑动&#xff0c;计算模版与&#xff08;图像被模版覆盖的地方&#xff…...

【算法刷题】Day7

文章目录 283. 移动零1089. 复写零 283. 移动零 原题链接 看到题目&#xff0c;首先看一下题干的要求&#xff0c;是在原数组内进行操作&#xff0c;平切保持非零元素的相对顺序 这个时候我们看到了示例一&#xff1a; [ 0, 1, 0, 3,12 ] 这个时候输出成为了 [ 1, 3, 12, 0, …...

前端 | iframe框架标签应用

文章目录 &#x1f4da;嵌入方式&#x1f4da;图表加载显示&#x1f4da;100%嵌入及滑动条问题&#x1f4da;加载动画保留 前情提要&#xff1a; 计划用iframe把画好的home1.html&#xff08;echarts各种图表组成的html数据大屏&#xff09;嵌入整合到index.html&#xff08;搭…...

linux -系统通用命令查询

有时候内网环境下&#xff0c;系统有些命令没有安装因此掌握一些通用的linux 命令也可以帮助我们解决一些问题查看 1.查看系统内核版本 uname -r2.查看系统版本 cat /etc/os-release3. 查看cpu 配置 lscpu4.查看内存信息 free [参数] 中各个数值的解释如下表 数值解释t…...

python炒股自动化(1),量化交易接口区别

要实现股票量化程序化自动化&#xff0c;就需要券商提供的API接口&#xff0c;重点是个人账户小散户可以申请开通&#xff0c;上手要简单&#xff0c;接口要足够全面&#xff0c;功能完善&#xff0c;首先&#xff0c;第一步就是要找对渠道和方法&#xff0c;这里我们不讨论量化…...

LeetCode(35)螺旋矩阵【矩阵】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 54. 螺旋矩阵 1.题目 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a…...

BeanUtil.copyProperties的优化与使用(解决copyProperties null值覆盖问题)

BeanUtil.copyProperties的优化与使用 前言一、copyProperties是什么&#xff1f;二、使用步骤1.引入库2.基础使用3.进阶使用4.实用场景 总结 前言 BeanUtil.copyProperties的优化与使用 一、copyProperties是什么&#xff1f; 在java中&#xff0c;我们想要将一个类的值赋值…...

Redis基本操作及使用

&#x1f4d1;前言 本文主要是【Redis】——Redis基本操作及使用的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304;每日一…...

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的镜像源&#xff0c;包括阿里的、网易的&#xff0c;还有很多教育网的源&#xff0c;比如&#xff1a;清华源、中科大源。推荐使用中科大源&#xff0c;快得很。 /etc/apt/sources.list编辑/etc/apt/sources.list文件, 在文件最前面添加以下条目(操作前…...

如何给shopify的网址做301跳转

很多shopify的运营者或者推广者由于缺货或者货物变更&#xff0c;又或者自己更换了使用的主题&#xff0c;导致自己的URL结构发生了变化&#xff0c;由于不想浪费掉自己原有URL 的流量&#xff0c;就想做个301跳转&#xff0c;让自己新的网址来承接原有的流量。接下来给大家介绍…...

Redis之秒杀系统

目录 Redis 秒杀 Mysql数据库设计 Mysql秒杀实现 MysqlRedis秒杀实现 秒杀是一种高并发场景&#xff0c;通常指的是在短时间内&#xff08;秒级别&#xff09;有大量用户同时访问某个商品或服务&#xff0c;争相抢购的情景。在这种情况下&#xff0c;系统需要处理大量并发请…...

c++基础----new

c基础----new 在C中&#xff0c;new是一个运算符&#xff0c;用于动态分配内存并返回指向该内存的指针。它可以用于创建单个对象、数组以及动态分配的对象。 下面是new的几种常见用法&#xff1a; 动态分配单个对象&#xff1a; int* ptr new int; // 动态分配一个int类型…...

Java中的mysql——面试题+答案(存储过程,外键,隔离级别,性能优化)——第23期

当涉及MySQL时&#xff0c;面试题的范围可以涵盖数据库设计、优化、复制、分片等方面。 什么是数据库范式&#xff1f;为什么要遵循数据库范式&#xff1f; 答案&#xff1a; 数据库范式是一组规范&#xff0c;用于设计关系数据库表的结构&#xff0c;以减少数据冗余和提高数据…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...