1.划分为k个相等的子集

题目描述：

给定一个整数数组nums和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 leetcode 698 leetcode 473

  1. 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
  2. 输出： True
  3. 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

回溯 + 剪枝

  1. 首先对数组求和，判断所有数的和是否能够整除k，不能直接return false;
  2. 对数组降序排列，首先安排最大的数能够减少很多不必要的分支，小的数有更加灵活的选择；
  3. 剪枝思路1：超过sum/ k 直接返回false

  4. 剪枝思路2：如果bucket[i] == 0，说明该桶分配元素失败（给该桶分配这个任务后所有的尝试都是失败的），则剪枝，因为也没必要再往后试了，其余桶也会出现一样的情况

    class Solution {
 int sum = 0;
 int target = 0;
 int[] bucket; 

 public boolean canPartitionKSubsets(int[] nums, int k) {
     bucket = new int[k]; // 分桶

     int sum = getSum(nums);
     if(sum % k != 0) return false; // 不能平分，返回false
     target = sum / k;

     Arrays.sort(nums);
     reverse(nums); // 从大到小排列，优先排好大的，方便剪枝

     if(nums[0] > target) return false; // 最大值大于target，返回false

     return backtrack(0,nums);
 }
 //树高：数组长度 树宽：桶的个数 
 private boolean backtrack(int idx, int[] nums){
     if(idx == nums.length) return true;

     // 将当前nums[idx] 分给 某一个桶
     for(int i = 0 ; i < bucket.length; i++){
         if(bucket[i] + nums[idx] > target) continue;

         bucket[i] += nums[idx];
         if(backtrack(idx + 1, nums)){
             return true;
         }
         bucket[i] -= nums[idx];

         //一个都放不进去，别试了
         if(bucket[i] == 0){
             return false;
         }       
     }
     return false;      
 }

 private int getSum(int[] nums){
     int ans = 0;
     for( int num : nums){
         ans += num;
     }
     return ans;
 }

 private void reverse(int[] nums){
     int left = 0;
     int right = nums.length - 1;

     while(left < right){
         int tmp = nums[left];
         nums[left] = nums[right];
         nums[right] = tmp;

         left++;
         right--;

     }
 }
}

2.完成所有工作的最短时间

题目描述：

给定一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。 将这些工作分配给 k 位工人，每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。给出分配方案使工人的 最大工作时间最小化 。返回分配方案中最小的最大工作时间 。 leetcode 1723 

输入：jobs = [1,2,4,7,8], k = 2         
输出：11
说明： 1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
      2 号工人：4、7（工作时间 = 4 + 7 = 11） 因此最大工作时间是 11 。

二分 + 回溯

  • K 个桶，每个桶的容量大小为target，如果在这个target下，工作能分完，这个方案是可行的，如果在这个target下分不完，那这个方案不可行。
  • 在每个target下测试能否尽可能的放置在k个桶中（回溯）。
  • 桶的最小容量设置为数组元素的最大值，因为如果桶容量小于组元素的最大值，工作没法分配。

  • 桶的最大容量设置为数组元素之和，即全部元素分给一个桶。

    class Solution {
  int[] bucket; 
  int[] jobs;
  public int minimumTimeRequired(int[] jobs, int k) {
      this.jobs = jobs;
      this.bucket = new int[k];
      int left = 0;
      int right = 0;

      for(int job : jobs){
          left = Math.max(left,job);
          right += job;
      }

      Arrays.sort(jobs); //排序，方便剪枝

      while(left < right){
          Arrays.fill(bucket,0); // 在每次回溯时，将桶的状态清零

          int mid = left + (right - left) / 2;
          if(canWork(jobs.length - 1, mid)){
              right = mid;
          }else{
              left = mid + 1;
          }
      }

      return left;
  }

  private boolean canWork(int idx, int target){
      if(idx == -1) return true; //从后往前放置元素，先放最大的

      for(int i = 0 ; i < bucket.length ; i++){
          if(bucket[i] + jobs[idx] > target) continue;

          bucket[i] += jobs[idx];

          if(canWork(idx - 1, target)){
              return true;
          }

          bucket[i] -= jobs[idx];

          // 如果这个工人分活失败（给他分配这个任务后所有的尝试都是失败的），则剪枝，
          // 因为也没必要再往后试了，其他人也会出现一样的情况
          if(bucket[i] == 0){
              return false;
          }
      }
      return false;
  } 
}