【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性

2024-02-16 21:36
文章标签 动态 规划 搜索 最小 压缩 状态 记忆 兼容性 1681

本文主要是介绍【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

本文涉及知识点

动态规划汇总
状态压缩 记忆化搜索

1681. 最小不兼容性

给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。
一个子集的 不兼容性 是该子集里面最大值和最小值的差。
请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。
子集的定义是数组中一些数字的集合，对数字顺序没有要求。
示例 1：
输入：nums = [1,2,1,4], k = 2
输出：4
解释：最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。
示例 2：
输入：nums = [6,3,8,1,3,1,2,2], k = 4
输出：6
解释：最优的子集分配为 [1,2]，[2,3]，[6,8] 和 [1,3] 。
不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。
示例 3：
输入：nums = [5,3,3,6,3,3], k = 3
输出：-1
解释：没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。
提示：
1 <= k <= nums.length <= 16
nums.length 能被 k 整除。
1 <= nums[i] <= nums.length

动态规划

对nums按升序排序。

动态规划的状态表示

pre[mask][end] 记录最小不兼容性和。mask表示nums中那些元素已经选择，选择的数优先放组号小的组。1组满了后，才放2组；2组满了，才放三组 ⋯ \cdots ⋯

动态规划的转移方程

mask1 = mask | (1 << j )
end1 = j
j必须符合以下条件：

  • j未被使用。
  • 如果是某个组的首元素，可以选择任意元素。
  • 如果不是某个组的首元素，j > end。且nums[j] != nums[end]
    { d p [ m a s k 1 ] [ j ] = d p [ m a s k ] [ e n d ] 某组的首元素 d p [ m a s k 1 ] [ j ] = d p [ m a s k ] [ e n d ] + n u m s [ j ] − n u m s [ e n d ] 非组首元素 \begin{cases} dp[mask1][j]= dp[mask][end] & 某组的首元素\\ dp[mask1][j]= dp[mask][end] + nums[j]-nums[end] & 非组首元素 \end{cases} {dp[mask1][j]=dp[mask][end]dp[mask1][j]=dp[mask][end]+nums[j]−nums[end]​某组的首元素非组首元素​

动态规划的初始值

dp[0][0]全部为0，其它全部为10000。

动态规划的填表顺序

mask从小到大，枚举前置条件。

动态规划的返回值

dp.back()的最小值。

代码

核心代码

class Solution {
public:int minimumIncompatibility(vector<int>& nums, int k) {m_c = nums.size();m_iMaskCount = 1 << m_c;sort(nums.begin(), nums.end());vector<int> vBitCount(m_iMaskCount);for (int i = 1; i < m_iMaskCount; i++){vBitCount[i] = 1 + vBitCount[i & (i - 1)];}vector<vector<int>> dp(m_iMaskCount, vector<int>(m_c, m_iNotMay));dp[0][0] = 0;for (int mask = 0; mask < m_iMaskCount; mask++){bool bGroupFirst = (0 == vBitCount[mask] % (m_c / k));for (int end = 0; end < m_c; end++){for (int j = bGroupFirst ? 0 : (end + 1); j < m_c; j++){if ((1 << j) & mask){continue;//已经选择}if ((nums[j] == nums[end])&& (!bGroupFirst)){continue;//相同}	const int iNew = dp[mask][end] + (bGroupFirst ? 0 : (nums[j]-nums[end]));dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],iNew);}}}const int iRet = *std::min_element(dp.back().begin(), dp.back().end());return (iRet >= m_iNotMay) ? -1 : iRet;}int m_c, m_iMaskCount,m_iNotMay=10000;
};

测试用例


template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{	vector<int> nums;int k;{Solution sln;nums = { 1 }, k = 1;auto res = sln.minimumIncompatibility(nums, k);Assert(res, 0);}{Solution sln;nums = { 1,1 }, k = 1;auto res = sln.minimumIncompatibility(nums, k);Assert(res, -1);}{Solution sln;nums = { 1, 2, 1, 4 }, k = 2;auto res = sln.minimumIncompatibility(nums, k);Assert(res, 4);}{Solution sln;nums = { 6, 3, 8, 1, 3, 1, 2, 2 }, k = 4;auto res = sln.minimumIncompatibility(nums, k);Assert(res, 6);}{Solution sln;nums = { 5,3,3,6,3,3 }, k = 3;auto res = sln.minimumIncompatibility(nums, k);Assert(res, -1);}{Solution sln;nums = { 11,11,3,4,2,16,14,13,6,14,2,5,10,13,5,7 }, k = 8;auto res = sln.minimumIncompatibility(nums, k);Assert(res, 12);}
}

记忆化搜索+动态规划

从后置条件倒推前置条件，可以省去大量不必要的状态。运行速度提高500%。缺点可理解性大幅降低。
mask 选择了那些数，end 是最一个数。如果本组只有一个数，则最小不兼容性和就是 除本数外 的前几个完整的组的最小不兼容性和。
如果完整的组，最后一个元素一定是最大值。最大值一定是某个组的最后一个。将此组调到最后一组，结果不变。
EndZeroCount 从右到左为1的第一个下标（从0开始）。为了一致，nums降序排序。
每组一个元素要特殊处理。

int EndZeroCount(unsigned x )
{for (int i = 0; i < 32; i++){if ((1 << i) & x){return i;}}return 32;
}class Solution {
public:int minimumIncompatibility(vector<int>& nums, int k) {m_c = nums.size();m_iMaskCount = 1 << m_c;m_pre = m_c / k;if (1 == m_pre){return 0;}		sort(nums.begin(), nums.end(),std::greater<>());m_nums = nums;m_vBitCount.resize(m_iMaskCount);for (int i = 1; i < m_iMaskCount; i++){m_vBitCount[i] = 1 + m_vBitCount[i & (i - 1)];}m_dp.assign(m_iMaskCount, vector<int>(m_c, m_iNotMay));const int iRet = Rec(m_iMaskCount-1);return (iRet >= m_iNotMay) ? -1 : iRet;}int Rec(int mask, int end){if (0 == mask){return 0;}auto& res = m_dp[mask][end];if (m_iNotMay != res){return res;}const int iPreMask = mask ^ (1 << end);const int cnt = m_vBitCount[mask] % m_pre;//最后一组数量if (1 == cnt ){return res = Rec(iPreMask);}for (int i = end+1 ; i < m_c; i++){if ((1 << i) & mask){if (m_nums[i] != m_nums[end]){res = min(res, Rec(iPreMask,i)+ m_nums[end]-m_nums[i]);}}}return res;}int Rec(int mask){return Rec(mask, EndZeroCount(mask));}int m_c, m_iMaskCount,m_iNotMay=10000, m_pre;vector<int> m_vBitCount;vector<vector<int>> m_dp;vector<int> m_nums;
};

2023年2月版

class Solution {
public:
int minimumIncompatibility(vector& nums, int k) {
m_c = nums.size();
if (k == m_c)
{
return 0;
}
if (1 == k)
{
std::set setNums(nums.begin(), nums.end());
if (nums.size() != setNums.size())
{
return -1;
}
return *setNums.rbegin() - *setNums.begin();
}
std::sort(nums.begin(),nums.end());
m_iMaskNum = (1 << m_c )*m_c;
m_vMaskByBits.resize(m_c + 1);
m_vMaskByBits[0].push_back(0);
vector vMaskBits(m_iMaskNum);
for (int mask = 1; mask < m_iMaskNum; mask++)
{
const int iSelMask = mask / m_c;
vMaskBits[mask] = vMaskBits[(iSelMask&(iSelMask - 1))m_c] + 1;
m_vMaskByBits[vMaskBits[mask]].push_back(mask);
}
m_vMaskGroupFirstToMin.resize(m_iMaskNum, m_iNotMay);
m_vMaskGroupFirstToMin[0] = 0;
for (int i = 0; i < nums.size(); i++)
{
vector dp(m_iMaskNum, m_iNotMay);
for (int iMask : m_vMaskByBits[i])
{
if (m_iNotMay == m_vMaskGroupFirstToMin[iMask])
{
continue;
}
const int iSelMask = iMask / m_c;
const int iPreSel = iMask% m_c;
if (0 == i % (m_c/k))
{//新组
for (int j = 0; j < m_c; j++)
{
if (iSelMask & (1 << j))
{
continue;
}
const int iNewMask = JoinMask(iSelMask | (1 << j), j);
dp[iNewMask] = min(dp[iNewMask], min(m_vMaskGroupFirstToMin[iMask],dp[iMask]));
}
}
else
{
for (int j = iPreSel+1; j < m_c; j++)
{
if (iSelMask & (1 << j))
{
continue;
}
const int iAdd = nums[j] - nums[iPreSel];
if (0 == iAdd)
{
continue;
}
const int iNewMask = JoinMask(iSelMask | (1 << j), j);
dp[iNewMask] = min(dp[iNewMask], min(m_vMaskGroupFirstToMin[iMask], dp[iMask]) + iAdd);
}
}
}
m_vMaskGroupFirstToMin.swap(dp);
}
std::set setRet;
for (int iPre = 0; iPre < m_c; iPre++)
{
int iIndex = (1 << m_c) - 1;
iIndex = iIndexm_c + iPre;
setRet.insert(m_vMaskGroupFirstToMin[iIndex]);
}
int iMin = setRet.begin();
return (m_iNotMay == iMin) ? -1 : iMin;
}
int JoinMask(int iSelMask, int iNewSelIndex)
{
return iSelMaskm_c + iNewSelIndex;
}
vector m_vMaskGroupFirstToMin;
int m_c;
int m_iMaskNum;
vector<vector> m_vMaskByBits;
const int m_iNotMay = 1000 * 1000;
};

2023年9月版

class Solution {
public:
int minimumIncompatibility(vector& nums, int k) {
m_c = nums.size();
if (k == m_c)
{
return 0;
}
m_iMaskNum = 1 << m_c;
if (0 != m_c % k)
{
return -1;
}
const int iNumOfAGroup = m_c / k;
vector<vector> vBitMask(m_c+1);
vBitMask[0].emplace_back(0);
for (int mask = 1; mask < m_iMaskNum; mask++)
{
vBitMask[bitcount((unsigned int)mask)].emplace_back(mask);
}
std::unordered_map<int, int> mMaskCom;
for (int mask : vBitMask[iNumOfAGroup])
{
int iMax = INT_MIN, iMin = INT_MAX;
unordered_set setValues;
for (int j = 0; j < m_c; j++)
{
if (mask & (1 << j))
{
MaxSelf(&iMax, nums[j]);
MinSelf(&iMin, nums[j]);
setValues.emplace(nums[j]);
}
}
if (setValues.size() != iNumOfAGroup)
{
continue;
}
mMaskCom[mask] = iMax - iMin;
}
int pre[1 << 16] = { 0 };
for (const auto& it : mMaskCom)
{
pre[it.first] = it.second;
}
for (int i = 2; i <= k; i++)
{
int dp[1 << 16] = { 0 };
for (const int& mask : vBitMask[iNumOfAGroup*i])
{
for (int sub = mask; sub; sub = (sub - 1) & mask)
{
if ((0 != pre[sub])&& mMaskCom.count(mask - sub))
{
int iNew = pre[sub] + mMaskCom[mask - sub];
if (0 != dp[mask])
{
iNew = min(iNew, dp[mask]);
}
dp[mask] = iNew;
}
}
}
memcpy(pre, dp, sizeof(dp));
}
return pre[m_iMaskNum - 1] ? pre[m_iMaskNum - 1] : -1;
}
int m_c, m_iMaskNum;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/715768。

相关文章

HTML5 搜索框Search Box详解

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具，能够有效提升用户体验,通过结合自动补全功能和适当的样式，可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框（Search Box）详解搜索框是一个用于输入查询内容的控件，通常用于网站或应用程
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...
MyBatis编写嵌套子查询的动态SQL实践详解

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可
阅读更多...
IIS 7.0 及更高版本中的 FTP 状态代码

IIS 7.0 及更高版本中的 FTP 状态代码

《IIS7.0及更高版本中的FTP状态代码》本文介绍IIS7.0中的FTP状态代码,方便大家在使用iis中发现ftp的问题... 简介尝试使用 FTP 访问运行 Internet Information Services （IIS） 7.0 或更高版本的服务器上的内容时，IIS 将返回指示响应状态的数字代
阅读更多...
Mybatis嵌套子查询动态SQL编写实践

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》：本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL
阅读更多...
SpringBoot实现文件记录日志及日志文件自动归档和压缩

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志，日志文件自动归档和压缩2.1、
阅读更多...
SpringBoot实现Kafka动态反序列化的完整代码

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题（Topic）的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht
阅读更多...
golang实现动态路由的项目实践

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体（数据库的定义）2.预加载preload3.添加关联的方法一、动态路由1
阅读更多...
Python Selenium动态渲染页面和抓取的使用指南

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模
阅读更多...
慢sql提前分析预警和动态sql替换-Mybatis-SQL

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2