【动态规划】【01背包 给定背包容量,装满背包最多有多少个物品】Leetcode 474. 一和零

2024-04-17 20:28

本文主要是介绍【动态规划】【01背包 给定背包容量,装满背包最多有多少个物品】Leetcode 474. 一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【动态规划】【01背包 给定背包容量,装满背包最多有多少个物品】Leetcode 474. 一和零

    • 解法

---------------🎈🎈474. 一和零 题目链接🎈🎈-------------------

纯 0 - 1 背包 是求 给定背包容量 装满背包 的最大价值是多少。
416. 分割等和子集是求 给定背包容量,能不能装满这个背包。
1049. 最后一块石头的重量 II是求 给定背包容量,尽可能装,最多能装多少
494. 目标和是求 给定背包容量,装满背包有多少种方法。
本题是求 给定背包容量,装满背包最多有多少个物品。

解法

😒: 我的代码实现============>

动规五部曲
相当于是一个背包——这里背包有两个维度:m个0,n个1,不同长度的字符串就是不同大小的待装物品。问尽量装满这个背包,里面能装最多多少物品

✒️确定dp数组以及下标的含义

dp[i][j]:容量为i个0和j个1的背包,能装下的子集最多个数为dp[i][j]。

✒️确定递推公式

dp[a][b] = Math.max( 表示不放当前物品dp[a][b], 表示添加当前物品dp[a-x][b-y]+1 )

✒️dp数组初始化

初始为0

✒️确定遍历顺序

01背包一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历

时间复杂度O(N)
空间复杂度O(N)

📘代码

class Solution {public int findMaxForm(String[] strs, int m, int n) {//0-1背包问题,相当于是m个0和n个1大小的背包,能装下多少元素// 【dp数组+初始化】dp[a][b] : a个0 b个1 大小的背包,能装下的最大子集个数  最终返回dp[m][n]即可 初始化全为0即可int[][] dp = new int[m+1][n+1];// 【遍历顺序】0-1背包问题 一个物品只能取一次,外层正向遍历物品,内层倒序遍历背包for(int i = 0; i < strs.length; i++){// 【遍历物品】,得到每个物品的x,y————0的个数,1的个数String str = strs[i];int x = 0; // 当前物品的0的个数int y = 0; // 当前物品的1的个数for(int p = 0; p < str.length(); p++){if(str.charAt(p) == '0'){x++;}if(str.charAt(p) == '1'){y++;}}for(int a = m; a>=x ; a--){ // 【倒序遍历这个二维背包,这里的顺序无所谓】for(int b = n; b>=y ; b--){//【递推公式】dp[a][b] = Math.max( 表示不放当前物品dp[a][b],  表示添加当前物品dp[a-x][b-y]+1 )dp[a][b] = Math.max(dp[a][b],  dp[a-x][b-y]+1);}}}return dp[m][n];}
}          

这篇关于【动态规划】【01背包 给定背包容量,装满背包最多有多少个物品】Leetcode 474. 一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

第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]代表

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n