[笔记]动态规划之01背包问题

2024-09-04 04:58

本文主要是介绍[笔记]动态规划之01背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

01背包

  • n件物品
  • w为容量上限的背包
  • weight[i]:第i件物品的重量
  • value[i]:第i件物品的价值

每件物品只能放入1次,装入哪些物品能让背包内物品总价值最高?

暴力解法:回溯算法 - 时间复杂度 O ( 2 n ) O(2^n) O(2n)

二维数组

  1. 确定dp数组下标含义

    dp[i][j] - 从下标为[0]到[i]的物品里取,放入容量为j的背包,此时的最大价值总和

  2. 确定递推公式

    • 不放物品i:dp[i][j] = dp[i - 1][j](物品重量大于背包容量,物品i放不进包里,背包价值不变;
    • 放物品i:dp[i][j] = dp[i - 1][j - weight[i]] + value[i]dp[i - 1][j - weight[i]]是容量为j - weight[i]时未放物品i的最大价值,dp[i - 1][j - weight[i]] + value[i]是此时放入物品i后背包的最大价值;
    • 综上:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
  3. 初始化dp数组

    1. 容量j为0时,背包价值总和一定为0;

    2. 当j < weight[0]时,dp[0][j] = 0(背包容量比第0号物品小,放不进背包);

    3. 当j > weight[0]时,dp[0][j] = value[0](背包可以放下第0号物品);

      //参考代码如下,全部初始化为0则可省略第一个for循环
      for (int j = 0; j < weight[0]; j++)dp[0][j] = 0;
      for (int j = weight[0]; j <= bagweight; j++) dp[0][j] = value[0];
      
  4. 确定遍历顺序

    1. 先遍历物品,后遍历背包
    2. 先遍历背包,后遍历物品
    3. 本质上:dp[i][j]由前序数据推出,for循环遍历次序不影响公式推导
  5. 举例推导dp数组

滚动数组

所谓滚动数组,就是通过一维数组的方式压缩存储背包问题的状态。

  1. 确定dp数组下标含义

    • dp[i][j] - 从下标为[0]到[i]的物品里取,放入容量为j的背包,此时的最大价值总和 ;
    • dp[j] - 容量为j的背包,所装物品的最大价值总和;
  2. 确定dp数组递推公式

    1. 不放物品i:dp[j] = dp[j]
    2. 放物品i:dp[j] = dp[j - weight[i]] + value[i]
    3. 综上,递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  3. 初始化dp数组

    • dp[0] = 0;
    • 其它下标可以初始化为0;
  4. 确定遍历顺序

    • 倒序遍历:保证物品i只被放入一次!

      dp[i][j]是由上一层dp[i - 1][ ]计算而来,当前层的dp[i][j]并不会被覆盖,顺序逆序遍历物品i都只被放入一次。如果顺序遍历dp[j]数组,就相当于dp[i][j]由层dp[i][ ]计算而来,这个过程就重复放入物品i了。

    • 先遍历物品,再嵌套遍历背包容量

      倒序遍历,如果先遍历背包容量,再嵌套物品,那么背包里都只放入了一个物品。

  5. 举例推导dp数组

这篇关于[笔记]动态规划之01背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135063

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监