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

发表于 分类于 阅读次数： Waline： 本文字数： 830 阅读时长 ≈ 3 分钟

考点

  • 分组背包
  • 贪心
  • 位运算

思路

基础优化DP

每行只能选一个，分组背包的裸题，f[i][j]即考虑前i个行，每行选一个的情况下和能组成j的可能性

这题难在优化，暴力DP直接看代码，要注意，背包上限是每行最大值之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    bool f[2][5000];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    int n = mat.size();
    int m = 0;
    for (int i = 1; i <= n; ++i) {
      int mx = 0;
      for (int& x : mat[i - 1]) mx = max(mx, x);
      m += mx;
      for (int j = 0; j <= m; ++j) {
        f[i & 1][j] = 0;
        for (int k = 0; k < mat[i - 1].size(); ++k) {
          if(j >= mat[i - 1][k])
          f[i & 1][j] |= f[i - 1 & 1][j - mat[i - 1][k]];
        }
      }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= m; ++i) {
      if (f[n & 1][i]) ans = min(ans, abs(i-target));
    }
    return ans;
  }
};

当然也可以压成一维，降低常数和空间开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    bool f[5000];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    int n = mat.size();
    int m = 0;
    for (int i = 1; i <= n; ++i) {
      int mx = 0;
      for (int& x : mat[i - 1]) mx = max(mx, x);
      m += mx;
      for (int j = m; j >= 0; --j) {
        f[j] = 0;
        for (int k = 0; k < mat[i - 1].size(); ++k) {
          if (j >= mat[i - 1][k]) f[j] |= f[j - mat[i - 1][k]];
        }
      }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= m; ++i) {
      if (f[i]) ans = min(ans, abs(i - target));
    }
    return ans;
  }
};

当然，直接用位运算替代会更加快：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    bitset<5005> f[2];
    f[0][0] = 1;
    for (int i = 0; i < mat.size(); ++i) {
      f[i + 1 & 1].reset();
      for (int j = 0; j < mat[i].size(); ++j) {
        f[i + 1 & 1] |= f[i & 1] << mat[i][j];
      }
    }
    int ans = inf;
    for (int i = 1; i <= 5000; ++i) {
      if (f[mat.size() & 1].test(i)) ans = min(ans, abs(i - target));
    }
    return ans;
  }
};

贪心优化DP

从Push方向的角度考虑问题，即已知f[i]，要拿去更新f[i+1]

和只会出现两种情况，小于等于target，大于target

由于我们需要求最接近target的数，也就是说，要么是小于等于target里最大的，要么是大于target里最小的

所以如果目标和小于等于target，正常更新；对于目标和大于target的情况，我们只想保留其中最小的和

截止第i个组出现的大于target的最小和，只有可能从两个地方出现：

  1. 前i - 1个组的和没有大于target，第i个组选了之后大于target
  2. 前i - 1个组的和已经大于target，在考虑第i个组后依然大于target，但反而可能比第一种情况更小

可以得到如下代码

还有一个易错点，这里是不可以滚动数组的！因为把k放到了外围循环，j的旧值基本都会被覆盖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    int n = mat.size();
    bool f[2][805];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    int pres = inf;
    for (int i = 0; i < n; ++i) {
      memset(f[i + 1 & 1], 0, sizeof(f[i + 1 & 1]));
      int tmx = inf;
      for (int k = 0; k < mat[i].size(); ++k) {
        int x = mat[i][k];
        for (int j = 0; j <= target; ++j) {
          if (!f[i & 1][j]) continue;
          int nxt = j + x;
          if (nxt > target)
            tmx = min(tmx, nxt);
          else
            f[i + 1 & 1][nxt] = 1;
        }
        if (pres != inf) tmx = min(tmx, pres + x);
      }
      pres = tmx;
    }
    int ans = inf;
    if (pres != inf) ans = min(ans, pres - target);
    for (int i = target; i >= 0; --i) {
      if (f[n & 1][i]) {
        ans = min(ans, target - i);
        break;
      }
    }
    return ans;
  }
};