Java 中集合位计数最多为 K 的最大整数

给定一个整数数组 nums[] 和一个正整数 K，任务是找出可以从数组中选择的最大数值数量，使得其二进制表示中的 1 的总数最多为 K。

示例 1

输入

int arr[] = {1, 3, 7, 8, 9};

int K = 6;

输出

集合二进制位之和最多为 K 的最大数值数量为 3

解释

对于给定的数组 {1, 3, 7, 8, 9}，考虑 1、3 和 7 的二进制表示中 1 的总和为 6，等于 K，因此可以选择的最大数字数量是 3。

示例 2

输入

int arr[] = {2, 5, 6, 10, 12};

int K = 5;

输出

集合二进制位之和最多为 K 的最大数值数量为 3

解释

对于给定的数组 {2, 5, 6, 10, 12}，考虑 2、5 和 6 的二进制表示中 1 的总和为 5，等于 K，因此可以选择的最大数字数量是 3。

示例 3

输入

int arr[] = {3, 4, 5, 15, 31};

int K = 8;

输出

集合二进制位之和最多为 K 的最大数值数量为 4

解释

对于给定的数组 {3, 4, 5, 15, 31}，考虑 3、4、31 和 15 的二进制表示中 1 的总和为 8，等于 K，因此可以选择的最大数字数量是 4。

方法：使用动态规划

算法

步骤 1：创建一个名为 dp 的二维数组。该数组的 dp[i][j] 变量表示可以从数组的前 i 个元素中选择的整数数量，使得其二进制表示中的 1 的总数最多为 j。

步骤 2：可以使用递归公式来填充 dp 数组。

步骤 2.1：如果 bit_sum 是 nums[i - 1] 的二进制形式中的 1 的数量，则 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - bit_sum] + 1)，依此类推。

步骤 3：返回 dp[n][k]，其中 n 是 nums 数组的长度，k 是给定的整数。

实施

文件名：LargestIntegersSum.java

输出

 
The total number of values with sum of setbits atmost K is 3

复杂度分析

上述代码的时间复杂度为 O(N * K)，其中 K 是给定的整数，N 是 nums 数组的长度。由于使用了大小为 N * K 的二维数组，空间复杂度也为 O(N * K)。