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

时间:2024-02-11 23:38:48 标签:  背包  

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. 遍历顺序

外层遍历物体,内层分别遍历背包容量的两个维度,且倒序遍历。在下面的文章中讲过具体细节:https://leetcode.cn/problems/ones-and-zeroes/submissions/501607337/

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])
来源:分享自作者个人站点/博客

智能推荐

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

标签:背包  

目录 动态规划:01背包理论基础416. 分割等和子集 动态规划:01背包理论基础

标签:子集  

1049. 最后一块石头的重量Ⅱ 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 思路 尽量将石头分为重量相同的两堆,这样两堆中的石头相撞之后剩下的石头就会最小。根据之前的01背包理论: 代码随想录算法训练营第四十五天(动态规划篇)|01背包-CSDN博客 代码随想录算法训练营第四十六天(动态规划篇)|01背包(滚动数组方法)-CSDN博客

标签:算法  

题目: 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元

标签:背包  

代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV 题目 https://www.acwing.com/problem/content/3/

标签:组合  

完全背包理论基础 完全背包与01背包只相差在物品是无限取用的。因此和01背包相比第二层对背包容量的遍历应该是正序的,而且正因为这个正序,使得在纯完全背包问题中,背包容量和物品的遍历是可以

标签:组合  

题目&#xff1a;01背包问题 文章链接&#xff1a;代码随想录 视频链接&#xff1a;LeetCode:背包问题 题目链接&#xff1a;卡码题目链接 图释&#xff1a; //二维dp数组实现#include <bits/stdc&#43;&#43;.h>using namespace std;int n,

标签:背包  

代码随想录算法训练营第四十二天| 01背包问题、416.分割等和子集 题目 https://www.acwing.com/problem/content/2/ 2.01背包问题

标签:子集  

416. 分割等和子集 题目链接&#xff1a;416. 分割等和子集 - 力扣&#xff08;LeetCode&#xff09; 思路 回溯——超时 首先想到之前的回溯算法&#xff0c;寻找数组中加和等于sum(nums)/2的子集&#xff0c;但对于大数组超时了&#xff1a; class Solution(object):def backtracking(self, nums, startIdx, curSum):if curSum > sum

标签:子集  

目录 139.单词拆分 方法一&#xff1a;回溯法 算法实现

标签:背包  

仅做学习笔记&#xff0c;详细请访问代码随想录 ● 理论基础 ● 77. 组合 ● 理论基础 回溯法解决的问题 回溯法&#xff0c;一般可以解决如下几种问题&#xff1a; 组合问题&#xf

标签:组合  

文章目录 01背包问题 二维思路代码 01背包问题&#xff08;滚动数组&#xff09;思路代码

标签:数组  

代码随想录算法训练营第十一天 | 二叉树基础 文章目录 代码随想录算法训练营第十一天 | 二叉树基础1 二叉树的理论基础1.1 二叉树的类型1

标签:算法  

代码随想录算法训练营第二十四天|回溯算法的理论基础、77. 组合 回溯算法的理论基础77. 组合 回溯算法的理论基础 这里我觉得《代码随想录》和y总的课都比较好了

标签:算法  

系列文章目录 代码随想录算法训练营第一天|数组理论基础&#xff0c;704. 二分查找&#xff0c;27. 移除元素 代码随想录算法训练营第二天|977.有序数组的平方 &#xff0c;209.长度最小的子数组 &#xff0c;59.螺旋矩阵II

标签:算法  

理论基础 代码随想录原文 什么是回溯法 回溯也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 回溯是递

标签:算法  

回溯算法&#xff1a;其实就是递归&#xff0c;但是其更加考虑是归这个过程&#xff01;得到的是最后的几种可能性&#xff01; 其适合几种问题&#xff1a; 1.组合问题&#xff1b;2.排列问题&#xff1b;3.子集

标签:组合  

77. 组合 题目链接&#xff1a;组合 题目描述&#xff1a; 给定两个整数

标签:组合  

本题力扣上没有&#xff0c;是刷的卡码网第52题52. 携带研究材料感兴趣的小伙伴可以去刷一下&#xff0c;是ACM模式。 题目&#xff1a; 题目描述&#xff1a; 小明是一位科学家&#xff0

标签:背包  

今日任务  回溯法理论基础 回溯的效率 回溯解决的问题 如何理解回溯 回溯法模板  7

标签:组合  

理论基础 回溯是递归的副产品&#xff0c;有递归就会有回溯。回溯算法的本质就是穷举&#xff0c;因此效率并不高&#xff0c;顶多采用剪枝的方式使之高效一些。 可以解决的问题&#xff1a;

标签:算法  

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第一行两个整数&#xff0c;N&#xff0c;V&#xff0c;用空格隔开&#xff0c;分别表示物品数量和背包容积。 接下来有 N 行&#xff0c;每行两个整数 vi,wi&#xff0c;用空格隔开&#xff0c;分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数&#xff0c;表示最大价值

标签:背包  

01背包问题 动态规划 01背包问题 动态规划写了点代码 C#实现程序运行结果代码和程序已经上传 01背包问题 动态规

标签:背包  

猜你喜欢

嗨害嗨,作业来喽背包问题01背包和完全背包问题都是一个背景下的:我有一个容量为M的背包,现在地上有N个物品,我跟个小偷似的眼里只有i个物品的价值vi和重量wi,现在我要做的就是为了偷的东西更值钱拿走一些东西,使它们的价值是所有方案里最大的01背包背景如上,01背包就是我眼前的这些东西都是孤品,只有一件,求最大价值。那么有些人会先想到:我可不

标签:背包  

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi &#xff0c;价值是 wi 。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超

标签:背包  

题目详情题目的大意是这样的:在一个洞穴中有n件宝物,每个宝物有重量、价值以及距离属性。所谓的距离属性是指从任意一个地方到这个宝物的位置需要耗费的路程时间。洞穴中除了宝物,还有一个魔王,魔王最开始是处于沉睡状态的,一旦魔王苏醒后,探险者将被魔王杀害而无法出洞,魔王的睡眠时间是wakeTime。此外,探险者拥有一个背包,背包的最大容量是packageSize,他可以采集任意的宝物,而且采集一个宝物的时间需要耗费1。问题是:如何在魔王苏醒时间之前采集到价值尽量大的宝物,要求采集到的宝物总重量不能超出背包容量,结果需要输出可以采集到的宝物id数组。题

标签:背包  路径  动态  

文章目录 二叉树基础二叉树种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 二叉树的存储方

标签:二叉树  

文章目录 344.反转字符串&#xff1a;双指针思路代码&#xff1a; 541. 反转字符串II思路&#

标签:字符串  

文章目录 理论基础![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/09da30301c104f02baf792ccbf39da15.png)效率回溯

标签:组合  

动态规划part01 理论基础509. 斐波那契数70. 爬楼梯解题思路 746. 使用最小花费爬楼梯解题

标签:爬楼梯  

题目&#xff1a; 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘&#43;’ 或 ‘-’ &#xff0c;然后串联起所有整数&#xff0c;可以构造一个 表达式 例如&#xff0c;

标签:背包  

代码随想录 (programmercarl.com) 647. 回文子串 1.dp数组及下标含义 我们在判断字符串S是否是回文&#xff0c;那么如果我们知道 s[1]&#xff0c;s[2]&#xff0c;s[3] 这个子串是回文的&#xff0c;那么只需要比较 s[0]和s[4]这两个元素是否相同&#xff0c;如果相同的话&#xff0c;这个字符串s 就是回文串。 布尔类型的dp[i][j]&#xff1a;表示区间范围[i,j] &#xff08;注意是左闭右闭&#xff09;的子串是否是回文子串&#xff0c;如果是dp[i][j]为true&#xf

标签:回文  

第七章 回溯算法 77.组合代码随想录文章详解总结 77.组合 以n&#61;5,k&#61;3为例

标签:算法  

数组理论基础 一维数组 数组中的元素在内存空间中是连续的数组名与数组中第一个元素的地址相同&#xff08;一维数组&#xff09;数组的下标从0开始删除数组的元素其实是用后面的元

标签:数组  

数组理论基础 一维数组 数组中的元素在内存空间中是连续的数组名与数组中第一个元素的地址相同&#xff08;一维数组&#xff09;

标签:数组  

动态规划理论基础 动态规划适用于解决有重叠子问题的问题。所以动态规划中的每一个状态一定是由上一个状态推导来的&#xff0c;这一点区分于贪心&#xff0c;因为贪心每一步总是取局部最优。 解题步骤&#xff1a;

标签:爬楼梯  

背包问题动态规划思路:状态表示 f(i, j)状态由几维表示表示的集合是什么所有选法选法条件只考虑前i个物品总体积 <= j集合的属性是什么最大值最小值元素的数量

标签:背包  动态  

题目&#xff1a;62.不同路径 文章链接&#xff1a;代码随想录 视频链接&#xff1a;LeetCode:62.不同路径 题目链接&#xff1a;力扣题目链接 图释&#xff1a; class Solution {public:// 确定dp数组&#xff08;dp table

标签:路径  

代码随想录算法训练营第五十九天|503.下一个更大元素II 、42. 接雨水 下一个更大元素II 503.下一个更大元素II文章讲解&#xff1a;https://programmercarl.com/0503.%E4%B8

标签:更大  

目录 理论基础  455.分发饼干  &#x1f4a1;解题思路

标签:大子  

代码随想录算法刷题训练营day16&#xff1a;LeetCode(104)二叉树的最大深度 、LeetCode(559)n叉树的最大深度、LeetCode(111)二叉树的最小深度、LeetCode(222)完全二叉树的节点个数 LeetCod

标签:算法  

代码随想录算法刷题训练营day15&#xff1a;LeetCode(226)翻转二叉树、LeetCode(101)对称二叉树 LeetCode(226)翻转二叉树 题目

标签:算法  

代码随想录算法刷题训练营day20&#xff1a;LeetCode(654)最大二叉树、LeetCode(617)合并二叉树、LeetCode(700)二叉搜索树中的搜索、LeetCode(700)二叉搜索树中的搜索、LeetCode(98)验证二叉搜索

标签:算法  

&#x1f9d1;‍&#x1f4bb; 文章作者&#xff1a;Iareges &#x1f517; 博客主页&#xff1a;https://blog.csdn.net/raelum ⚠️ 转载请注明出处

标签:背包  

目标和(放满背包的方法有几种)力扣题目链接(opens new window)难度:中等给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例:输入:nums: [1, 1, 1, 1, 1], S: 3输出:5解释:-1+1+1+1+1 = 3+1-1+1+

标签:写法  背包  实战  状态  目标  

454、四数相加Ⅱ·map哈希表当初不知四数相加的好,做完四数之和发现~oh 这题真简单题目链接:https://leetcode.cn/problems/4sum-ii/前提:计算四个数组中多少个元组满足条件(值可以重复)思路:四个数组分别两两相加|时间复杂度O(n^2)   前两个数组相加的值作为map的键   map中查找等于(0-后两个数组相加的值)的键   找到则+该键值(这个值可能大于一)代码实现:unordered_map哈希

标签:之和  赎金  算法  训练营  第七天  

算法训练DAY24|回溯1 第77题. 组合 力扣题目链接 给定两个整数 n 和 k&#xff0c;返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n &#61; 4, k &#61; 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 上面我们说了要解决 n为100&#xff0c;k为50的情况&#xff0c;暴力写法需要嵌套50层for循环&#xff0c;那么回溯法就用递归来解决嵌套层数的问题。 递归来做层叠嵌套&#xff08;可以理解是开k层for循环&#xff09;

标签:算法  

相关问题

相关文章

热门文章

推荐文章

相关标签