首页 > 其他分享 >DP问题空间的优化

DP问题空间的优化

时间:2024-11-06 18:09:39浏览次数:1  
标签:int 用到 枚举 层数 一维 空间 include 优化 DP

1. 消去作为“层数”的那一维

如果状态转移时需要用到这一层和上一层的信息,此时往往需要改变枚举顺序
例如:\(01\) 背包

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N], v[N];
int f[2][N], n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )   cin >> w[i] >> v[i];
    
    for(int i = 1; i <= n; i ++ )
    
        for(int j = 0; j <= m; j ++ )
        {
            f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j]);
            if(j >= w[i])    f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - w[i]] + v[i]);
        }
    
    cout << f[n & 1][m] << endl;
    
}

2. 将作为“层数”的那一维修改为滚动数组

如果状态转移只会用到这一层和上一层的信息,说明任意时刻我们只会用到两层的信息,因此“层数”那一维只需要两层即可
例如:\(01\) 背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m;
int f[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) {
        int v, w;   cin >> v >> w;
        for(int j = m; j >= v; j -- ) {  // !!!改变枚举顺序
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[m] << endl;
    return 0;
}

3. 总结

通过代码可以看出来:
[消去维度方法]空间节省的更多,毕竟它直接把一维消去了;但是对于可能需要修改代码逻辑(例如枚举顺序)。
[滚动数组方法]空间消耗是[消去维度方法]的两倍;但是它实现起来比较简单,只需要在所有用到层数那一维的地方加上 & 1 即可。

标签:int,用到,枚举,层数,一维,空间,include,优化,DP
From: https://www.cnblogs.com/ALaterStart/p/18530724

相关文章

  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......
  • 在VS Code打开的文件夹或工作空间中忽略某些文件和文件夹
    使用快捷键Ctrl+,打开Setting窗口。可以看到有三个级别的Settings,我想针对本工作空间进行设置,所以选择Workspace。选择右上角的OpenSettings(JSON)图标。添加需要忽略的文件或文件夹。"settings":{ "files.exclude":{ "**/.git":true, "**/.sv......
  • 252 摸鱼 压缩dp
    /*http://oj.daimayuan.top/course/5/problem/252蜗蜗一共有n天假期,在假期的第i天摸鱼他会得到ai的快乐值。如果蜗蜗每天都摸鱼的话,他会有愧疚感,所以蜗蜗制定了这么个计划:对于每一天,蜗蜗都有一个列表,如果蜗蜗在列表中的每一天都在摸鱼的话,这一天蜗蜗就不能摸鱼。现在请问......
  • Python 爬取大量数据如何并发抓取与性能优化
    Python并发抓取与性能优化在进行网络爬虫开发时,爬取大量数据可能非常耗时。尤其是在处理许多网页或API请求时,逐个请求速度会非常慢。为了解决这个问题,我们可以通过并发抓取提高爬取效率。同时,通过性能优化来进一步减少耗时和资源占用,使爬虫更高效。本篇文章将带大家了解......
  • MySQL 索引的底层实现原理与优化策略
    在数据库中,索引是提升查询性能的关键工具。MySQL中的索引机制可以显著加快数据检索速度,尤其在数据量庞大的情况下,合理使用索引可以使得原本耗时的操作变得高效。然而,滥用或错误地使用索引也可能对性能产生负面影响。本文将深入探讨MySQL索引的底层实现原理、常用类型及其......
  • 实践中如何优化 MySQL:深入剖析与策略分享
    MySQL作为一款广泛应用的关系型数据库管理系统,在企业级应用和互联网服务中扮演着重要的角色。然而,随着业务规模的增长和数据量的增加,如何有效地优化MySQL性能,确保系统在高并发、大数据量的环境下仍能高效运行,成为开发者和数据库管理员的重要课题。本文将深入探讨MySQL......
  • Node.js-增强 API 安全性和性能优化
    ​......
  • 详解UDP协议
    UDP是一种无连接的、简单的传输层协议,UDP协议的设计目的是提供一种简单、轻量级的通信机制,适用于那些对实时性和传输效率有较高要求,但对数据完整性和可靠性要求相对较低的应用。UDP协议报头UDP协议的报头部分由四部分组成:源端口号,目的端口号,UDP长度,校验和。源端口号:识别发......
  • 【多微电网】基于粒子群优化算法的面向配电网的多微电网协调运行与优化(Matlab代码实现
     ......
  • 网站元素审查修改,轻松优化网页内容
    理解网站元素审查的重要性网站元素审查是指检查和修改网页上的各种元素,如文本、图片、按钮、表单等,以确保它们的功能和表现符合预期。这不仅有助于提升用户体验,还能优化SEO和网站性能。常见的审查内容包括内容准确性、样式一致性、交互功能、响应式设计等。备份网站文件......