区块链技术博客
www.b2bchain.cn

子集划分是个什么东西?背包问题->动态规划?

这篇文章主要介绍了子集划分是个什么东西?背包问题->动态规划?的讲解,通过具体代码实例进行19471 讲解,并且分析了子集划分是个什么东西?背包问题->动态规划?的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=19471

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

子集划分是个什么东西?背包问题->动态规划?

    • 子集划分问题抽取
    • 子集划分问题解决思路
    • 其他题目

子集划分问题抽取

子集划分是个什么东西?背包问题->动态规划?
以上题目来自力扣494.目标和,本篇文章的重点在于提取出其中的一种类型问题,称为子集划分问题

所谓子集划分问题,是一个典型的背包问题,而背包问题,使用的是动态规划来解决。此题可以使用回溯方法来做,但由于一些重复的计算,时间复杂度会很高,因此可以转化为背包问题从而使用动态规划来解决来降低复杂度。

子集划分问题解决思路

子集划分问题,其实就是我们把nums数组分成两个子集A和B,分别代表分配+和分配-的数,那么他们和S会存在以下关系:

//计算nums中有几个子集的和为sum int howManySubsets(int[] nums,int sum){ 	 int n=nums.length; 	 //dp[i][j]=x表示在前i个物品中选择,若当前背包容量为j,则最多有x种方法能恰好装满背包       int[][] dp=new int[n+1][sum+1];      for(int i=0;i<=n;i++){          //dp[..][0]=1 如果背包最大载重为0 那什么都不装是一种          //dp[0][..]=0 没有物品,则无法装包          dp[i][0]=1;      }      for(int i=1;i<=n;i++){         for(int j=0;j<=sum;j++){            if(j>=nums[i-1]){                  //等于放入与不放入二者之和                  dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];              }else{                  //背包空间不足 只能不放                  dp[i][j]=dp[i-1][j];              }          }      }      return dp[n][sum]; } //函数 int findTargetSumWays(int[] nums,int S){ 	int sum=0; 	for(int n:nums){ 		sum+=n; 	} 	if(sum<S||(sum+target)%2==1){ 		return 0; 	} 	return howManySubsets(nums,(sum+target)/2; 	 } 

其他题目

像其他问题也可以使用这种解法,例如416.分割等和子集
子集划分是个什么东西?背包问题->动态规划?

class Solution {     public boolean canPartition(int[] nums) {         int sum=0;         for(int num:nums){             sum+=num;         }         if(sum%2==1) return false;         int target=sum/2;         boolean[][] dp=new boolean[nums.length][target+1];         //第一个只能装满容积为第一个大小的背包         if(nums[0]<=target){             dp[0][nums[0]]=true;         }         for(int i=1;i<nums.length;i++){             for(int j=0;j<=target;j++){                 dp[i][j]=dp[i-1][j];                  if(nums[i]==j){                     dp[i][j]=true;                     continue;                 }                 if(nums[i]<j){                     dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];                 }             }         }         return dp[nums.length-1][target];     } } 

本文转自互联网,侵权联系删除子集划分是个什么东西?背包问题->动态规划?

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 子集划分是个什么东西?背包问题->动态规划?
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们