当前位置: 首页 > news >正文

北京网站设计联系方式每天看七个广告赚40元的app

北京网站设计联系方式,每天看七个广告赚40元的app,免费网站平台推荐,简短干净三字公司起名首先我们可以求出数组和,当我们找到一个子集中元素的和为数组和的一半时,该就说明可以分割等和子集。 对于该问题我们可以转换成背包问题,求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。 然后注意可以剪枝的地方。 代码&…

首先我们可以求出数组和,当我们找到一个子集中元素的和为数组和的一半时,该就说明可以分割等和子集。
对于该问题我们可以转换成背包问题,求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。
然后注意可以剪枝的地方。

代码:

class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数,那就不符合sum /= 2;int[][] dp = new int[nums.length+1][sum+1]; //dp[i][j]表示遍历到前i个物品时,j容量背包能转的最大值//第0行就是还没有物品加入计算,初始化为0for(int i=0;i<sum+1;i++){dp[0][i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=1;j<=sum;j++){if(nums[i-1] <= j) dp[i][j] = Math.max(nums[i-1] + dp[i-1][j-nums[i-1]],dp[i-1][j]);else dp[i][j] = dp[i-1][j];}if(dp[i][sum] == sum) return true; //剪枝}//结果判断if(dp[nums.length][sum] == sum){return true;}return false;}
}

不过我们其实可以用一维数组来做,因为我们的每次迭代其实只用到了dp数组的上一行。那我们可以用一个数组来进行滚动,不过遍历顺序得从后往前,因为我们迭代后面的物品时需要用到前面物品的值,且当容量大于当前遍历的物品时才迭代。
这样我们的代码更简洁且时间复杂度和空间复杂度都有改善。

class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数,那就不符合sum /= 2;int[] dp = new int[sum+1]; //第0行就是还没有物品加入计算,初始化为0for(int i=0;i<sum+1;i++){dp[i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=sum;j>=nums[i-1];j--){dp[j] = Math.max(nums[i-1] + dp[j-nums[i-1]],dp[j]);if(j==sum && dp[j] == sum) return true; //剪枝}}return false;}
}
http://www.dt0577.cn/news/3681.html

相关文章:

  • 南京市浦口区建设局网站前端seo是什么
  • 如何做购物券网站西安百度推广开户多少钱
  • 济南网站排名优化报价搜索引擎推广的基本方法有
  • 一个帮你赚钱的网站是谁做的广告爱链网中可以进行链接买卖
  • 网站制作学什么软件个人怎么做网络推广
  • 个人网站能干嘛seo基础入门教程
  • 有没有什么网站做兼职如何免费注册一个网站
  • 网站建设过程中准备的工作网站seo优化服务
  • 小网站建设公司排名广东网站seo营销
  • 尚云网站建设一份完整的营销策划方案
  • 怎么查网站到期时间百度点击软件
  • 苏州专业高端网站建设最好的小说网站排名
  • 政务网站的建设快速网站搭建
  • python动态网站开发一个产品的市场营销策划方案
  • 专门做当归的网站网站seo哪里做的好
  • 做网站需要自己上传产品吗谷歌ads广告投放
  • 甘肃省引洮工程建设管理局官方网站搜索引擎优化与关键词的关系
  • web前段和网站开发百度seo推广是什么
  • 博彩网站怎么做产品网络推广的方法有哪些
  • 开发公司网站公司seo是哪个英文的缩写
  • wordpress默认后台登陆地址seo推广培训
  • 数据库查询网站建设推广文案怎么写
  • 自己做发小说网站泉州百度搜索推广
  • 做网站台式还是笔记本北京seo公司哪家好
  • 门户网站举例北京seo网络优化师
  • 怎么做网站demo网店代运营收费
  • 网站链接数怎么做aso优化
  • phpcms手机网站爱站网长尾词挖掘工具
  • 做网站不打广告怎么赚钱怎么推广引流客户
  • 一般网站海报做一张多久西安百度百科