代码随想录算法训练营第四十九天(动态规划篇)| 474. 一和零, 完全背包理论基础

news/2024/4/17 17:54:28

474. 一和零

题目链接:https://leetcode.cn/problems/ones-and-zeroes/submissions/501607337/

思路

之前的背包问题中,我们对背包的限制是容量,即每个背包装的物品的重量和不超过给定容量,这道题的限制是0和1的个数,因此这个背包是二维m和n,最多可以装m个0和n个1。数组中的每个元素都是一个物体,包含若干个0和1。

1. dp数组定义

dp[i][j]: 最多装i个0和j个1的背包最多能装dp[i][j]个物体。

2. 递推公式

遍历每个物体,这个物体有x个0和y个1,我们选择装或者不装这个物体。如果不装它,那么背包中的物体保持原样,如果装它,就要为它腾出相应的0和1的位置,腾出后背包能最多装dp[i-x][j-y]个物体,再加上当前物体,即dp[i-x][j-y]+1,因此递推公式为:

dp[i][j] = max(dp[i][j], dp[i-x][j-y]+1)

3. 初始条件

01背包的dp数组初始化为0就可以。

4. 遍历顺序

外层遍历物体,内层分别遍历背包容量的两个维度,且倒序遍历。在下面的文章中讲过具体细节:代码随想录算法训练营第四十六天(动态规划篇)|01背包(滚动数组方法)-CSDN博客

5. 举例推导dp数组

以输入:["10","0001","111001","1","0"],m = 3,n = 3为例

最后dp数组的状态如下所示:

代码实现

class Solution(object):def findMaxForm(self, strs, m, n):  # m个0,n个1dp = [[0]*(n+1) for _ in range(m+1)]# zeros, ones = 0, 0for s in strs:zeros = s.count('0')ones = s.count('1')for i in range(m, zeros-1, -1):for j in range(n, ones-1, -1):dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)return dp[m][n]

完全背包理论基础

题目链接:题目页面

思路

完全背包允许物体被重复放入,它的代码与01背包的区别在于遍历顺序。01背包对内部容量的循环是从大到小遍历,为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的,所以要从小到大去遍历。

代码实现

N, V = map(int, input().split())
weight, value = [0]*N,[0]*N
for i in range(N):weight[i], value[i] = map(int,input().split())dp = [0]*(V+1)
for i in range(N):for j in range(weight[i], V+1):dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
print(dp[j])


https://www.xjx100.cn/news/3271459.html

相关文章

【芯片设计- RTL 数字逻辑设计入门 15 -- 函数实现数据大小端转换】

文章目录 函数实现数据大小端转换函数语法函数使用的规则Verilog and Testbench综合图VCS 仿真波形 函数实现数据大小端转换 在数字芯片设计中,经常把实现特定功能的模块编写成函数,在需要的时候再在主模块中调用,以提高代码的复用性和提高设…

算法学习——LeetCode力扣二叉树篇4

算法学习——LeetCode力扣二叉树篇4 222. 完全二叉树的节点个数 222. 完全二叉树的节点个数 - 力扣(LeetCode) 描述 给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。 完全二叉树 的定义如下:在完全二叉树中&#xf…

【项目日记(九)】项目整体测试,优化以及缺陷分析

💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:项目日记-高并发内存池⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你做项目   🔝🔝 开发环境: Visual Studio 2022 项目日…

C#,21根火柴棍问题(21 Matchticks Problem)的算法与源代码

一、21根火柴棍问题(21 Matchticks Problem) 21根火柴棍问题是西方经典游戏之一。 给定21根火柴,2个人A和B(比如:分别是计算机和用户)。 每个人一次可以挑选 1-- 4 根火柴。 被迫挑最后一根火柴的人输了…

java中ArrayList类常用API

前言:在学习java的ArrayList类的时候,有很多的API需要了解,下面我将举出其中在新手学习时使用频率较大的几个API。 先大体看一下有哪几个:(如图) 目录 1.add() 解释: …

Ubuntu Desktop - Terminal 输出全部选中 + 复制

Ubuntu Desktop - Terminal 输出全部选中 复制 1. Terminal2. Terminal 最大化3. Edit -> Select All4. Copy & PasteReferences 1. Terminal 2. Terminal 最大化 3. Edit -> Select All 4. Copy & Paste Edit -> Copy or Shift Ctrl C Edit -> Paste…

时间序列预测——BiGRU模型

时间序列预测——BiGRU模型 时间序列预测是指根据历史数据的模式来预测未来时间点的值或趋势的过程。在深度学习领域,循环神经网络(Recurrent Neural Networks, RNNs)是常用于时间序列预测的模型之一。在RNNs的基础上,GRU&#x…