本文涉及知识点
C++动态规划
位运算、状态压缩、枚举子集汇总
LeetCode2172. 数组的最大与和
给你一个长度为 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
状态机动态规划
动态规划的状态
dp’[i][mask] 表示处理完前i个数组,篮子的状态为mask的最大与和。
令k=2 × \times ×(j-1) 第j个篮子的状态由k位和k+1位表示。两位都是0表示篮子为空;k位为1,k+1位0表示篮子有一个空位;k+1位为1,k位为0,忽略;两位都为1,表示篮子满了。
pre = dp’[i] dp=dp’[i+1]
用滚动数组的空间复杂度为:O(4numSlots)
如果自己编码、解码空间复杂度可以降到O(3numSlots)
动态规划的转移方程
枚举nums[i]放到第j个篮子。单状态转移的时间复杂度:O(1)。
总时间复杂度:O(n3numSlotsm+n4numSlots) ≈ \approx ≈ 8 × \times × 106
注意:非法状态必须提前结束。
动态规划的初始值
pre[0]为0,其余全部为-1
动态规划的填表顺序
i从小到大
动态规划的返回值
max(pre)
代码
核心代码
class Solution {
public:int maximumANDSum(vector<int>& nums, int M) {const int N = nums.size();const int iMaskCnt = 1 << (2 * M);vector<int> pre(iMaskCnt, -1);pre[0] = 0;for (int i = 0; i < N; i++) {vector<int> dp(iMaskCnt, -1);for (int p = 0; p < iMaskCnt; p++) {if (-1 == pre[p]) { continue; }for (int j = 0; j < M; j++) {const int k = 2 * j;const bool b1 = p & (1 << k);const bool b2 = p & (1 << (k + 1));const int iAdd = (j + 1) & nums[i];if (b1 & b2) { continue; }if (b1) {const int nM = p | (1 << (k + 1));dp[nM] = max(dp[nM], pre[p] + iAdd);}else {const int nM = p | (1 << k);dp[nM] = max(dp[nM], pre[p] + iAdd);}}}pre.swap(dp);}return *std::max_element(pre.begin(), pre.end());}
};
单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1, double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> nums;int numSlots;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){nums = { 1, 2, 3, 4, 5, 6 }, numSlots = 3;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(9, res);}TEST_METHOD(TestMethod01){nums = { 1,3,10,4,7,1 }, numSlots = 9;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(24, res);}TEST_METHOD(TestMethod02){nums = {1 }, numSlots = 1;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(1, res);}TEST_METHOD(TestMethod03){nums = { 1 ,2}, numSlots = 1;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(1, res);}TEST_METHOD(TestMethod04){nums = { 1 ,2 }, numSlots = 2;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(3, res);}};
}
扩展阅读
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。