• 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); 非零下标初始最大值。

  • 相关阅读:
    腾讯云Redis全面升级,性能提升400%,可用性高达5个9
    Ubuntu16.04上安装Docker
    我们总结了弹性伸缩的五个条件与六个教训
    if...else绝佳替换方案
    qt mingw 生成DUMP文件,和pdb文件
    调试-Debug
    SpringBoot 常用注解总结
    小谈设计模式(26)—中介者模式
    CSRF(Pikachu靶场练习)
    一个命令就可启用的微信机器人WhoChat
  • 原文地址:https://blog.csdn.net/qq_63819197/article/details/134339830