首页 > 其他分享 >01背包&完全背包二维写法的对比,进而理解一维优化后的正逆序

01背包&完全背包二维写法的对比,进而理解一维优化后的正逆序

时间:2022-10-03 11:34:15浏览次数:92  
标签:背包 二维 01 一维 写法 逆序

01背包题解

完全背包题解

二维写法时两种背包问题核心代码的区别:

可以看出,01背包用的是上一层的数据,完全背包用的是当前层的数据
所以优化为一维时,
01背包需逆序

    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

完全背包需正序

    for (int i = 1; i <= n; i ++) 
        for (int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

标签:背包,二维,01,一维,写法,逆序
From: https://www.cnblogs.com/LHgogo/p/16750201.html

相关文章

  • 2018-2019 ACM-ICPC, Asia Seoul Regional Contest(CF GYM 101987) Problem K. TV Sho
    ProblemSolution设\(p_{i,R/B}\)为第\(i\)号节点染成R或B所代表的点。考虑2-SAT,对于每一个猜的操作,其中任意一个与猜的答案颜色不同,则其他两个必须相同。我们暴力进行......
  • 01-Elasticsearch[简介, 核心术语, 架构原理, 倒排索引]
    什么是分布式搜索引擎搜素引擎分布式存储与搜索Lucene,Solr,ES倒排序索引Lucene是类库solr基于LuceneES基于LuceneES核心术语ES集群架构原理倒排索引......
  • 01-分布式会话[会话的定义, 无状态会话, 有状态会话...]
    分布式会话什么是会话会话Session代表的是客户端与服务器的一次交互过程,这个过程可以是连续也可以是时断时续的。曾经的Servlet时代(jsp),一旦用户与服务端交互,服务器用户......
  • 学会 Git 01:Git 入门
    Git的数据库Git是一个分布式版本管理系统,可以在任何时间点将文件的状态作为更新记录保存起来。Git有以下两种数据库:远程数据库:有专有的服务器,可多人共享本地数据库......
  • 1106 2019数列——15分
    把2019各个数位上的数字2、0、1、9作为一个数列的前4项,用它们去构造一个无穷数列,其中第n(>4)项是它前4项之和的个位数字。例如第5项为2,因为2+0+1+9=12,个位数是......
  • 面试题 01.09. 字符串轮转(拼接)
    面试题01.09.字符串轮转(拼接)方法1就是二重循环暴力,为了节省空间可以利用取模的思想。时间复杂度:方法2就是用两倍,然后find是否为其子串即可。时间复杂度:......
  • 【Java】01基础-05 方法
    1.方法概述1.1方法的概念方法(method)是将具有独立功能的代码块组织成为一个整体,使其具有特殊功能的代码集注意:方法必须先创建才可以使用,该过程成为方法定义方法创建后并不......
  • 【Java】01基础-04数组
    1.数组1.1数组介绍数组就是存储数据长度固定的容器,存储多个数据的数据类型要一致。1.2数组的定义格式1.2.1第一种格式数据类型[]数组名示例:int[]arr;double[]......
  • 【Java】01基础-IDEA2021.3
    1、HelloIDEA......
  • 2022-2023-1 20221401 《计算机基础与程序设计》第五周学习总结
    2022-2023-120221401《计算机基础与程序设计》第五周学习总结作业信息班级链接https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求https://www......