Question

2172. 数组的最大与和

English Version

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。

你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。

• 比方说，将数字 [1, 3] 放入篮子 _1_ 中，[4, 6] 放入篮子 _2_ 中，这个方案的与和为 (1 AND _1_) + (3 AND _1_) + (4 AND _2_) + (6 AND _2_) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入_ _numSlots 个篮子中的最大与和。

 

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 _1_ 中，[2, 6] 放入篮子 _2_ 中，[3, 5] 放入篮子 _3_ 中。
最大与和为 (1 AND _1_) + (4 AND _1_) + (2 AND _2_) + (6 AND _2_) + (3 AND _3_) + (5 AND _3_) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 _1_ 中，[3] 放入篮子 _3_ 中，[4] 放入篮子 _4_ 中，[7] 放入篮子 _7_ 中，[10] 放入篮子 _9_ 中。
最大与和为 (1 AND _1_) + (1 AND _1_) + (3 AND _3_) + (4 AND _4_) + (7 AND _7_) + (10 AND _9_) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

 

提示：

• n == nums.length
• 1 <= numSlots <= 9
• 1 <= n <= 2 * numSlots
• 1 <= nums[i] <= 15

解法

方法一：状态压缩 + 动态规划

由于每个篮子最多只能放两个数，我们不妨将篮子数乘以 $2$，这样每个篮子最多只能放一个数。

接下来，我们定义 $f[i]$ 表示篮子状态为 $i$ 时的最大与和，其中 $i$ 是一个二进制数，表示每个篮子是否放了数。初始时 $f[0]=0$。

接下来，我们考虑 $f[i]$ 如何进行状态转移。

我们可以枚举 $i$，记 $i$ 的二进制表示中 $1$ 的个数为 $cnt$。如果 $cnt \gt n$，那么 $i$ 不是一个合法的状态，我们可以直接跳过。否则，我们可以枚举 $i$ 的二进制表示中的每一位 $j$，如果 $i$ 的第 $j$ 位为 $1$，那么我们可以将第 $(cnt-1)$ 个数 $nums[cnt-1]$ 放入第 $j$ 个篮子中，此时有：

$$ f[i] = \max{f[i], f[i \oplus (1 << j)] + (nums[cnt-1] \wedge (j / 2 + 1))} $$

其中 $\oplus$ 表示异或运算，而 $\wedge$ 表示按位与运算。

答案为 $\max{f[i]}$。

时间复杂度 $O(4^k \times k \times 2)$，空间复杂度 $O(4^k)$。其中 $k$ 表示篮子的数量，即题目中的 $numSlots$。

class Solution:
  def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
    n = len(nums)
    m = numSlots << 1
    f = [0] * (1 << m)
    for i in range(1 << m):
      cnt = i.bit_count()
      if cnt > n:
        continue
      for j in range(m):
        if i >> j & 1:
          f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))
    return max(f)

class Solution {
  public int maximumANDSum(int[] nums, int numSlots) {
    int n = nums.length;
    int m = numSlots << 1;
    int[] f = new int[1 << m];
    int ans = 0;
    for (int i = 0; i < 1 << m; ++i) {
      int cnt = Integer.bitCount(i);
      if (cnt > n) {
        continue;
      }
      for (int j = 0; j < m; ++j) {
        if ((i >> j & 1) == 1) {
          f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
        }
      }
      ans = Math.max(ans, f[i]);
    }
    return ans;
  }
}

class Solution {
public:
  int maximumANDSum(vector<int>& nums, int numSlots) {
    int n = nums.size();
    int m = numSlots << 1;
    int f[1 << m];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < 1 << m; ++i) {
      int cnt = __builtin_popcount(i);
      if (cnt > n) {
        continue;
      }
      for (int j = 0; j < m; ++j) {
        if (i >> j & 1) {
          f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
        }
      }
    }
    return *max_element(f, f + (1 << m));
  }
};

func maximumANDSum(nums []int, numSlots int) int {
  n := len(nums)
  m := numSlots << 1
  f := make([]int, 1<<m)
  for i := range f {
    cnt := bits.OnesCount(uint(i))
    if cnt > n {
      continue
    }
    for j := 0; j < m; j++ {
      if i>>j&1 == 1 {
        f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
      }
    }
  }
  return slices.Max(f)
}

function maximumANDSum(nums: number[], numSlots: number): number {
  const n = nums.length;
  const m = numSlots << 1;
  const f: number[] = new Array(1 << m).fill(0);
  for (let i = 0; i < 1 << m; ++i) {
    const cnt = i
      .toString(2)
      .split('')
      .filter(c => c === '1').length;
    if (cnt > n) {
      continue;
    }
    for (let j = 0; j < m; ++j) {
      if (((i >> j) & 1) === 1) {
        f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & ((j >> 1) + 1)));
      }
    }
  }
  return Math.max(...f);
}