蓝桥杯之【01背包模版】牛客例题展示

 牛客链接

#include <bits/stdc++.h>
using namespace std;
int n,V;
const int N=1010;
int v[N],w[N];
int dp[N][N];
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<dp[n][V]<<endl;

    memset(dp,0,sizeof(dp));
    for(int i=1;i<=V;i++)
    {
        dp[0][i]=-1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]&&dp[i-1][j-v[i]]!=-1)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout<<(dp[n][V]==-1?0:dp[n][V]);
    return 0;
}

优化:滚动数组

#include <bits/stdc++.h>
using namespace std;
int n,V;
const int N=1010;
int v[N],w[N];
int dp[N];
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<dp[V]<<endl;

    memset(dp,0,sizeof(dp));
    for(int j=1;j<=V;j++) dp[j]=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)
        {
            if(dp[j-v[i]]!=-1)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
    }
    cout<<(dp[V]==-1?0:dp[V]);
    return 0;
}

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

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

相关文章

力扣刷题Days16(js)-67二进制求和

目录 1,题目 2&#xff0c;代码 2.1转换进制数 2.2模拟加法 3&#xff0c;学习与总结 Math.floor() 模拟加法思路回顾 重点复习巩固 模拟加法的思路和学习位运算&#xff1b; 今天没精力了&#xff0c;先休息 1,题目 给你两个二进制字符串 a 和 b &#xff0c;以二进制…

CSS 用 flex 布局绘制骰子

<!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><style>.box {height: 100px;width: 100px;border: 2px solid grey;border-radius: 10px;display: flex;justify-content: center; // 水平居中/* alig…

桥接模式以及在JDBC源码剖析

介绍&#xff1a; 1、桥接模式是指&#xff1a;将实现和抽象放在两个不同类层次中&#xff0c;使两个层次可以独立改变 2、是一种结构型设计模式 3、Bridge模式基于类的最小设计原则&#xff0c;通过使用封装、聚合以及继承等行为让不同的类承担不同的职责。 4、特点&#xff1…

【DAY11 软考中级备考笔记】数据结构 查找和排序

数据结构 查找和排序 3月12日 – 天气&#xff1a;晴 1. 顺序查找 顺序查找就是简单的从头一个一个的进行比较&#xff0c;注意它的平均查找长度 2. 折半查找 折半查找和二叉排序树一致&#xff1a; 优点&#xff1a;查找效率很高 缺点&#xff1a;要求必须是循序存储并且表中…

LoadRunner学习:RuntimeSetting、参数化、关联、(unfinished

LoadRunner RuntimeSetting 运行时设置 在Vuser中设置Run-time Settings RunLogic&#xff1a;运行逻辑&#xff0c;决定了脚本真正执行逻辑&#xff0c; Init和End部分代码只能执行一次。决定脚本真正执行逻辑的意思是&#xff0c;在Run中的代码和Number of Iteration决定了…

马斯克放出豪言,他旗下的xAI要把Grok开源了

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

WeiPHP5.0远程代码执行漏洞

文章目录 前言声明一、漏洞描述二、影响版本三、漏洞复现四、修复建议 前言 weiphp 是一个开源&#xff0c;高效&#xff0c;简洁的微信开发平台 声明 请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后…

Learn OpenGL 08 颜色+基础光照+材质+光照贴图

我们在现实生活中看到某一物体的颜色并不是这个物体真正拥有的颜色&#xff0c;而是它所反射的(Reflected)颜色。物体的颜色为物体从一个光源反射各个颜色分量的大小。 创建光照场景 首先需要创建一个光源&#xff0c;因为我们以及有一个立方体数据&#xff0c;我们只需要进行…

04.JavaScript中的封装和函数

函数 理解函数的封装特性&#xff0c;掌握函数的语法规则 声明和调用 函数可以把具有相同或相似逻辑的代码“包裹”起来&#xff0c;通过函数调用执行这些被“包裹”的代码逻辑&#xff0c;这么做的优势是有利于精简代码方便复用。 声明&#xff08;定义&#xff09; 声明&a…

白嫖的学习资源,程序员绝对相见恨晚!

麦瑟尔夫说&#xff1a;厌学是心灵的癌症。 不学而原地踏步则会让你变成大笨蛋&#xff0c;甚至脑子瓦特......&#xff08;好吧&#xff0c;可以喷了&#xff0c;其实我在危言耸听&#xff09; 但是&#xff01;排除鸡汤的洗脑&#xff0c;学习的重要性是不可否认的&#xff…

初学者必会的Python3文件操作

文件操作的步骤&#xff1a; 打开文件 -> 操作文件 -> 关闭文件 切记&#xff1a;最后要关闭文件。 打开文件 文件句柄 open(文件路径, 模式) 指定文件编码 文件句柄 open(文件路径,模式,encodingutf-8) 为了防止忘记关闭文件&#xff0c;可以使用上下文管理器来…

大模型的整体性

大模型在人工智能领域&#xff0c;体现出一种高度的整体性特征。大模型的整体性表现在其能够跨越多种数据模态&#xff0c;统一表示&#xff0c;应用广泛的知识&#xff0c;以统一的方式处理复杂信息&#xff0c;并在多种场景下保持一致和有效的性能。这种整体性可以分为外部和…

PNG图片合成,带手机外观设置,可自定义金额等

PNG图片合成&#xff0c;带手机外观设置&#xff0c;可自定义金额等 软件界面成品显示免责声明 软件界面 成品显示 免责声明 若因使用代码与官方造成不必要的纠纷&#xff0c;本人盖不负责&#xff0c;存粹技术爱好&#xff0c;若侵犯贵公司的权益&#xff0c;请告知&#xff…

数据结构·二叉树(一)

1. 树概念及结构 1.1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;树叶朝下的。 有一个特殊的节点&#xff0c;称为根节点&#…

Redis核心数据结构之压缩列表(二)

压缩列表 压缩列表节点的构成 encoding 节点的encoding属性记录了节点的content属性所保存数据的类型及长度: 1.一字节、两字节或者五字节长&#xff0c;值得最高位为00、01或者10的是字节数组编码:这种编码表示节点的content属性保存着字节数组&#xff0c;数组的长度由编…

【Python】random库

专栏文章索引&#xff1a;Python 原文章&#xff1a;Python中random函数用法整理_python random-CSDN博客 目录 1.random.random() 2.random.uniform(a, b) 3.random.randint(a, b) 4.random.randrange([start], stop[, step]) 5. random.choice() 6. random.shuffle(x[,…

【每日八股】Java基础中面试你必须要掌握问题1

&#x1f525; 个人主页: 黑洞晓威 &#x1f600;你不必等到非常厉害&#xff0c;才敢开始&#xff0c;你需要开始&#xff0c;才会变的非常厉害。## 如何解决浮点数运算的精度丢失问题&#xff1f; BigDecimal 可以解决精度问题的原因在于它是一个精确的十进制数学运算类&…

idea中设置字段唯一,后台做出提示(springboot项目)

在项目中&#xff0c;我们通常需要对某些字段做字段唯一的限制&#xff0c;保证在数据库中该字段对应的值不能出现重复的值&#xff0c;接下来看看怎么做吧~ 数据库中可以同时设置几个字段的unique&#xff0c;就比如用户在进行注册的时候&#xff0c;一个用户只能对应一个电话…

爬虫入门到精通_框架篇14(PySpider架构概述及用法详解)

官方文档 Sample Code&#xff1a; from pyspider.libs.base_handler import *class Handler(BaseHandler):crawl_config {}# minutes24 * 60&#xff1a;每隔一天重新爬取every(minutes24 * 60)def on_start(self):self.crawl(http://scrapy.org/, callbackself.index_page)…

week07day01(powerbi)

一. Power BI简介 1. 构成部分 power query: 进行简单的数据清洗power pivot : 进行指标计算power view &#xff1a; 进行报表视图 二. Power Query (进行数据清洗) 1. 如何获取数据&#xff1a; 点击获取数据 ——> 选择导入数据的类型——> 会出现 "加载&…