【C++动态规划 分组背包】1981. 最小化目标值与所选元素的差|2009

server/2024/11/28 23:54:09/

本文涉及知识点

C++动态规划
C++背包问题

LeetCode1981. 最小化目标值与所选元素的差

给你一个大小为 m x n 的整数矩阵 mat 一个整数 target 。
从矩阵的 每一行 中选择一个整数,你的目标是 最小化 所有选中元素之 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a b 两数字的 绝对差 是 a - b 的绝对值。
示例 1:
在这里插入图片描述

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出:0
解释:一种可能的最优选择方案是:

  • 第一行选出 1
  • 第二行选出 5
  • 第三行选出 7
    所选元素的是 13 ,等于目标值,所以绝对差是 0 。
    示例 2:

在这里插入图片描述

输入:mat = [[1],[2],[3]], target = 100
输出:94
解释:唯一一种选择方案是:

  • 第一行选出 1
  • 第二行选出 2
  • 第三行选出 3
    所选元素的是 6 ,绝对差是 94 。
    示例 3:
    在这里插入图片描述

输入:mat = [[1,2,9,8,7]], target = 6
输出:1
解释:最优的选择方案是选出第一行的 7 。
绝对差是 1 。
提示:
m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800

动态规划 分组背包

动态规划的状态表示

dp1[i][m] 表示前i行是否存在为m的方案。m ∈ \in [0,target-1]$ dp2[i] 表示是否存在>=target,如果存在取最小值。不存在则为10000。由于网格(矩阵)全部为正整数,故只会越来越大。空间复杂度:O(mtarget)

动态规划的状态表示

枚举前置状态。
如果dp[i][m]成立,通过val枚举第i行:
dp[i+1][m+val] = true
dp[i+1][dp2[i]+val] = true
dp[i+1][x] = true,可以封装成立函数。枚举第i行,也可以封装成函数。
时间复杂度:O(mntarget)

动态规划的填表顺序

for i = 0 to m-1 枚举各例

动态规划的初始值

dp[0][0] = true,其它为false。

动态规划的返回值

dp1.back()[x]成立
min(min(abs(x-target)),abs(dp2.back()-target))

代码

核心代码

class Solution {public:int minimizeTheDifference(vector<vector<int>>& mat, int target) {vector<int> pre(target);pre[0] = true;int iPre = INT_MAX/10;for (const auto& v : mat) {vector<int> cur(target);int iCur = INT_MAX;auto Add = [&](int curV) {for (auto n : v) {const int iNew = curV + n;if (iNew >= target) {iCur = min(iCur, iNew);}else {cur[iNew] = true;}}};Add(iPre);for (int i = 0; i < target; i++) {if (pre[i]) { Add(i); }}swap(iPre, iCur);pre.swap(cur);}int ans = (iPre - target);for (int i = 0; i < target; i++) {if (pre[i]) { ans = min(ans, target - i); }}return ans;}};

单元测试

vector<vector<int>> mat;int target;TEST_METHOD(TestMethod11){mat = { {1,2,3},{4,5,6},{7,8,9} }, target = 13;auto res = Solution().minimizeTheDifference(mat, target);AssertEx(0, res);}TEST_METHOD(TestMethod12){mat = { {1},{2},{3} }, target = 100;auto res = Solution().minimizeTheDifference(mat, target);AssertEx(94, res);}TEST_METHOD(TestMethod13){mat = { {1,2,9,8,7} }, target = 6;auto res = Solution().minimizeTheDifference(mat, target);AssertEx(1, 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++**实现。


http://www.ppmy.cn/server/137669.html

相关文章

Python For循环

Python 的 for 循环是自动化重复任务的强大工具&#xff0c;可以使代码更高效、更易于管理。本教程将解释 for 循环的工作原理&#xff0c;探讨不同的应用场景&#xff0c;并提供大量实用示例。无论你是初学者还是希望提升技能的开发者&#xff0c;这些示例都将帮助你更好地在 …

虚拟dom

是什么 描述真实DOM的javaScript对象 //虚拟dom描述的对象const vdom {tag: div,props: {onclick: () > alert(clicked),},children: ["click me"]}渲染器 将虚拟dom渲染成真实dom 实现思路 创建元素 将vnode.tag作为标签名来创建元素给元素添加属性与事件 …

TensorFlow_T4 猴痘病识别

目录 一、前言 二、前期准备 1、设置GPU 2、导入数据 3、查看数据 三、数据预处理 1、加载数据 2、可视化数据 3、再次检查数据 4、配置数据集 四、构建CNN网络 五、编译 六、训练模型 七、模型评估 1、Loss and Acurracy图 2、指定图片进行预测 一、前言 &#…

香港将承办2025年全运会项目

行政長官在去年的施政報告中&#xff0c;表明政府會繼續以精英化、專業化、盛事化、產業化和普及化推動本港體育發展。隨着啟德體育園啟用在即&#xff0c;明年舉辦的第十五屆全國運動會&#xff0c;香港也會承辦當中八個競賽項目&#xff0c;相信屆時會將香港市民對體育運動的…

Vue学习笔记(十五)

文章目录 3.4. 【reactive 创建&#xff1a;对象类型的响应式数据】3.5. 【ref 创建&#xff1a;对象类型的响应式数据】3.6. 【ref 对比 reactive】3.7. 【toRefs 与 toRef】3.8. 【computed】3.9.【watch】\* 情况一\* 情况二\* 情况三\* 情况四\* 情况五 3.10. 【watchEffec…

使用Navicat连接远程服务器中在docker中运行的MySQL数据库保姆级教程

使用Navicat连接远程服务器中在docker中运行的MySQL数据库保姆级教程 一、需要的资源 Navicat客户端&#xff08;我使用的是17.0.8版本&#xff0c;安装教程B站搜一个&#xff0c;很快能解决&#xff09;服务器&#xff08;已安装docker并运行了MySQL&#xff09; 二、步骤 …

【AI开源项目】FastGPT- 快速部署FastGPT以及使用知识库的两种方式!

文章目录 一、FastGPT大模型介绍1. 开发团队2. 发展史3. 基本概念 二、FastGPT与其他大模型的对比三、使用 Docker Compose 快速部署 FastGPT1、安装 Docker 和 Docker Compose&#xff08;1&#xff09;. 安装 Docker&#xff08;2&#xff09;. 安装 Docker Compose&#xff…

Vite学习之模式

在安装了 Vite 的项目中&#xff0c;可以在 npm scripts 中使用 vite 可执行文件&#xff0c;下面是通过脚手架创建的 Vite 项目中默认的 npm scripts&#xff1a; 启动开发服务器&#xff08;dev命令&#xff09;——vite package.json {"scripts": {"dev&q…