码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 01背包和完全背包区别


    01背包和完全背包区别在于,对于物品拿一次和多次区别!!

    一、遍历次序

    01背包:只能是先物品,再背包;

    先背包后物品,那么只会在每一个背包里放0-i个物品的最大值。

    过程:先对最后一个背包,从第一个物品开始比较,放入第一个,对于更大的物品,就会覆盖之前的物品,最终导致有且仅有一个物品放入了背包。不符合。

    完全背包(解决装备容量为j的背包,最佳价值)

    可以先背包后物品,也可以先物品后背包。因为允许一个物品使用多次,同时,更新该状态的时候,只要保证前一个背包(物品)的状态更新过(存在了),那么该状态就能更新。

    二、遍历顺序

    01背包

    对于背包的遍历是逆序:保证了每一个物品,只拿一次。状态与上一层有关(放完i-1个物品之后),如果是正序,先更新第一个背包,到第二个背包的时候,得根据上一层的第一个背包和上一层的自身退出来,但是上一层的第1个背包已经被更新了,如果再拿更新过的来推导出,就会使用同一个物品。

    完全背包

    由于,完全背包一个物品可以被使用多次,所以正序。

    三、完全背包题目类型

    1、凑满容量j的最大价值。纯粹背包问题,dp[j] = max(dp[j], dp[j -weight[i]] + value[i])

    2、凑满容量j有几种方式。组合;先物品后背包。  排序:先背包,后物品。允许元素相同的集合

    dp[j] += dp[j-weight[i]];

    3、凑满容量j,最少需要几个元素.。dp[j] = min(dp[j], dp[j - weight[i]] + 1); 非零下标初始最大值。

  • 相关阅读:
    猿创征文|Docker实战:docker 安装mongodb
    springboot+jsp体育器材租赁java场地预约系统ssm
    kubernetes资源对象介绍及常用命令(三)
    如何制作一个卡刷扩容补丁。用于扩容系统等分区 刷写第三方需要扩容才可以刷写的系统或者GSI GSI系统bug修复【二】
    YBTOJ 状压dp合集
    【趣学算法】分治算法
    CentOS安装htop工具
    数字电路和模拟电路-9时序逻辑电路、计数器和寄存器
    MybatisPlus【SpringBoot】 6 插件 6.3 乐观锁
    TCP和UPD的区别
  • 原文地址:https://blog.csdn.net/qq_63819197/article/details/134339830
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号