Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1838221
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-05-09 23:47:15

刷题刷到这里,先说题目:给定一组字符串,其中每个字符串中只包含‘0’和‘1’,给定你m个0 和n 个1,求最多能排出多少个字符串。
乍一看这题,貌似在哪里见过,貌似又没见过,哎,一排脑袋,01背包,只不过变成了二维的。在此,我们就先复习一下一维的01背包问题,以备后用~~~
N个物品,每个价值value[i], 需要占用空间need[i],给定一个登山包(不知道哪年买的。。。),容量为M,求用该登山包装这N个物品,最大价值能装多少。
不多说,直接dp,递推公式为dp[i][j] = max(dp[i-1][j], dp[i-1][j-need[i]]+value[i]),第一版代码如下:


点击(此处)折叠或打开

  1. for( i = 1; i <=N ; ++i)
  2. {
  3.     for( j = 0; j <= M; j++)
  4.     {
  5.         if( j >= need[i] )
  6.             best[i][j] = max( best[i-1][j], best[i-1][j - need[i]] + value[i]);
  7.         else
  8.             best[i][j] = best[i-1][j];
  9.     }
  10. }

接下来考虑优化问题,这种递推能不能将空间复杂度降低至O(M)呢,答案是肯定的,请看下面的代码:

点击(此处)折叠或打开

  1. for( i = 1; i <=N ; ++i)
  2. {
  3.     for( j = M; j >= 0; --j)
  4.     {
  5.         if( j >= need[i] )
  6.             best[j] = max( best[j], best[j - need[i]] + value[i]);
  7.     }
  8. }

为什么对j要进行倒序遍历呢?这是因为在计算本轮第i个物品的时候,需要用到上一轮i-1个物品时的状态,而如果正向递增遍历,则会更新掉前面的数据,故采用倒叙遍历啦~~
有了如上的思路,变换为leetcode的题目,大家就不难找出解决思路了吧,先求出每个字符串对应需要的0和1的个数,相当于01背包中的need[i],给定的m和n相当于01背包中的背包容量M,代码如下:


点击(此处)折叠或打开

  1. int findMaxForm(vector<string>& strs, int m, int n){
  2.     int len = strs.size(), i, j, M, N;
  3.     if(len == 0||(m==0&&n==0)) return 0;
  4.     vector<vector<int>> dp(len, vector<int>(2, 0));
  5.     for(i = 0; i < len; i++)
  6.         for(j = 0; j < strs[i].length(); j++){
  7.             if(strs[i][j]=='0') dp[i][0]+=1;
  8.             else dp[i][1]+=1;
  9.         }
  10.     vector<vector<int>> res(m+1, vector<int>(n+1, 0));
  11.     for(i = 0; i < len; i++){
  12.         for(M=m; M>=0;M--)
  13.             for(N=n; N>=0;N--)
  14.                 if(M>=dp[i][0]&&N>=dp[i][1]){
  15.                     res[M][N]= max(res[M][N], res[M-dp[i][0]][N-dp[i][1]]+1);
  16.                 }
  17.     }
  18.     return res[m][n];
  19. }

谢谢大家观看~~~

阅读(2545) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~