LeetCode 474. 一和零(01背包动态规划)
发布日期:2021-07-01 03:25:57
浏览次数:2
分类:技术文章
本文共 1630 字,大约阅读时间需要 5 分钟。
1. 题目
在计算机界中,我们总是追求用有限的资源获取最大的收益。
现在,假设你分别支配着 m 个 0 和 n 个 1。另外,还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ,找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:给定 0 和 1 的数量都不会超过 100。给定字符串数组的长度不会超过 600。示例 1:输入: Array = { "10", "0001", "111001", "1", "0"}, m = 5, n = 3输出: 4解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出,即 "10","0001","1","0" 。示例 2:输入: Array = { "10", "0", "1"}, m = 1, n = 1输出: 2解释: 你可以拼出 "10",但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 0-1背包的变种,两个维度,背包容量为m,n, 求能装下的单词最多
class Solution { public: int findMaxForm(vector& strs, int m, int n) { int i, j, k, one, zero, len = strs.size(), maxcount = 0; vector > dp(m+1,vector (n+1,-1)); //dp[i][j] 表示使用i个0,j个1 时,对应的最大单词数个数 dp[0][0] = 0;//初始化 for(i = 0; i < len; ++i)//遍历每个单词 { one = count01(strs[i]); zero = strs[i].size()-one; for(j = m-zero; j >= 0; --j) { //逆序遍历,+one,zero后新生成的状态不会干扰本次 for(k = n-one; k >= 0; --k) { if(dp[j][k] != -1)//存在的状态 { //转移到的状态 dp[j+zero][k+one] dp[j+zero][k+one] = max(dp[j+zero][k+one], dp[j][k]+1); maxcount = max(maxcount, dp[j+zero][k+one]); } } } } return maxcount; } int count01(string &s) { int one = 0; for(int i = 0; i < s.size(); ++i) { if(s[i]=='1') one++; } return one; }};
转载地址:https://michael.blog.csdn.net/article/details/106256106 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月19日 17时40分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
kvm和远程管理工具virt-manager的部署
2019-05-02
Debian镜像源服务器的架设
2019-05-02
修改设备管理器信息,修改我的电脑系统属性,修改dxdiag信息
2019-05-02
Linux虚拟化技术Xen和KVM的优势特点对比
2019-05-02
泛虚拟化技术(以Xen为例)
2019-05-02
虚拟化技术未来发展趋势
2019-05-02
KVM虚拟机介绍
2019-05-02
libvirt命令行文档
2019-05-02
搭建本地Ubuntu 镜像服务器
2019-05-02
ubuntu12.04本地搭建ubuntu更新源
2019-05-02
Ubuntu装配宋体
2019-05-02
ssh 关闭后仍保持当前运行的进程
2019-05-02
超微X8DTL-3板载LSI M1068E阵列卡Linux驱动程序
2019-05-02
在Ubuntu上安装rpm文件方法(rpm转换成deb)
2019-05-02
ubuntu系统从中文环境改成英文环境
2019-05-02
ubuntu 12.10 软件更新源列表
2019-05-02
ubuntu下设置开机自启动项
2019-05-02
解决Windows 2008驱动安装失败
2019-05-02
netstat命令及日志分析命令
2019-05-02
Linux日志管理
2019-05-02