当前位置：首页 > news >正文

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

news 2024/11/1 13:33:57

本文涉及知识点

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);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功