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

背包问题leetcode

这篇文章主要介绍了背包问题leetcode,通过具体代码讲解8161并且分析了背包问题leetcode的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了背包问题leetcode。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8161.html。具体如下:

问题一:分割等和子集(LeetCode 416)

416. 分割等和子集   01背包

 //给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。  // // 注意:  // //  // 每个数组中的元素不会超过 100  // 数组的大小不会超过 200  //  // // 示例 1:  // // 输入: [1, 5, 11, 5] // //输出: true // //解释: 数组可以分割成 [1, 5, 5] 和 [11]. //  // //  // // 示例 2:  // // 输入: [1, 2, 3, 5] // //输出: false // //解释: 数组不能分割成两个元素和相等的子集. //  // //  // Related Topics 动态规划  // 👍 343 👎 0   //leetcode submit region begin(Prohibit modification and deletion) class Solution {     public boolean canPartition(int[] nums) {         int sum = 0;         //计算数组的和sum,如果sum为奇数,那肯定不能分成两部分,直接返回false         for(int i = 0; i<nums.length; i++) sum += nums[i];         if(sum % 2 != 0) return false;         sum = sum/2;         //初始化base case :dp[...][0] = true,相当于当载重量为0的时候,肯定什么东西也不用放,背包肯定默认是满的,因为载重量为0嘛,所以是true;dp[0][...] = false,相当于在任一载重量时,什么东西都不放,那肯定背包没有满,所以是false         boolean[][] dp = new boolean[nums.length+1][sum+1];         for(int i = 0; i<nums.length+1; i++) dp[i][0] = true;         //这里可以省略,因为java中boolean量默认是false,这里没有注释掉是因为想把逻辑表达清楚。         for(int i = 0; i<sum+1; i++) dp[0][i] = false;          //数字索引         for(int i = 1; i<=nums.length; i++){             //背包容量 所剩距离target的数字             for(int j = 1; j<=sum; j++){                 //如果当前的背包容量比要放的数量都小,那就没法放,只能继承之前的状态                 if(j < nums[i-1]) dp[i][j] = dp[i-1][j];                 else{                     //不放入 或者 放入,不管哪种状态,只要能放满就可以                     dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];                 }             }         }         return dp[nums.length][sum];     } }   //leetcode submit region end(Prohibit modification and deletion) 
 public class Solution {      public boolean canPartition(int[] nums) {         int len = nums.length;         if (len == 0) {             return false;         }          int sum = 0;         for (int num : nums) {             sum += num;         }          if ((sum & 1) == 1) {             return false;         }          int target = sum / 2;          //建立dp数组,dp[i]表示能否找到和为i的数组元素集合         boolean[] dp = new boolean[target + 1];         dp[0] = true;          if (nums[0] <= target)   dp[nums[0]] = true;           for (int i = 1; i < len; i++) {             for (int j = target; nums[i] <= j; j--) {                 //提前结束                 if (dp[target])   return true;                  //不选当前元素  选当前元素                 dp[j] = dp[j] || dp[j - nums[i]];             }         }         return dp[target];     } }   

322. 零钱兑换   完全背包

 //给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 // -1。  // //  // // 示例 1:  // // 输入: coins = [1, 2, 5], amount = 11 //输出: 3  //解释: 11 = 5 + 5 + 1  // // 示例 2:  // // 输入: coins = [2], amount = 3 //输出: -1  // //  // // 说明:  //你可以认为每种硬币的数量是无限的。  // Related Topics 动态规划   import java.util.Arrays;  //leetcode submit region begin(Prohibit modification and deletion) import java.util.Arrays;  public class Solution {      public int coinChange(int[] coins, int amount) {         //总体积amount  单个消费coins[i]         //构成amount金额 最少硬币个数         //恰好为amount 所以初始值设置为amount+1不可达   不存在设置为0可以不选的状态         int[] dp = new int[amount + 1];         Arrays.fill(dp, amount + 1);         dp[0] = 0;          for (int coin : coins) {             for (int i = coin; i <= amount; i++) {                 //不选和 选                 dp[i] = Math.min(dp[i], dp[i - coin] + 1);             }         }          if (dp[amount] == amount + 1) {             dp[amount] = -1;         }         return dp[amount];     } }   //leetcode submit region end(Prohibit modification and deletion) 

 

本文地址https://www.b2bchain.cn/8161.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 背包问题leetcode
分享到: 更多 (0)

评论 抢沙发

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

b2b链

联系我们联系我们