2218. 从栈中取出 K 个硬币的最大面值和

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

考点

  • 分组背包
  • 前缀和

思路

假设有个容量为3的栈，那么它可以产生：

  • 体积为1，价值为a[0]
  • 体积为2，价值为a[0] + a[1]
  • 体积为3，价值为a[0] + a[1] + a[2]

三种情况选一个，是分组背包的裸题，直接看代码

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:
  static const int neg = 0xcfcfcfcf;
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    // f[i][j]: 前i组物品，背包容量达到j下的和，取最大值
    int f[1005][2005];
    int n = piles.size();
    memset(f, 0xcf, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) {
        f[i][j] = max(f[i][j], f[i - 1][j]);
        int s = 0;
        for (int k = 0; k < piles[i-1].size(); ++k) {
          s += piles[i-1][k];
          int w = k + 1, v = s;
          if (j >= w)
            f[i][j] = max(f[i][j], f[i - 1][j - w] + v);
          else
            break;
        }
      }
    }
    return f[n][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
class Solution {
 public:
  static const int neg = 0xcfcfcfcf;
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    // f[i][j]: 前i组物品，背包容量达到j下的和，取最大值
    int f[2005];
    int n = piles.size();
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = k; j >=0 ; --j) {
        int s = 0;
        for (int k = 0; k < piles[i - 1].size(); ++k) {
          s += piles[i - 1][k];
          int w = k + 1, v = s;
          if (j >= w)
            f[j] = max(f[j], f[j - w] + v);
          else
            break;
        }
      }
    }
    return f[k];
  }
};

当然还可以再优化，提前用前缀和避免后续的重复计算

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
class Solution {
 public:
  static const int neg = 0xcfcfcfcf;
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    // f[i][j]: 前i组物品，背包容量达到j下的和，取最大值
    int f[2005];
    int n = piles.size();
    int pre[2005];
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      memset(pre, 0, sizeof(pre));
      for (int k = 1; k <= piles[i - 1].size(); ++k) {
        pre[k] = pre[k - 1] + piles[i - 1][k - 1];
      }
      for (int j = k; j >= 0; --j) {
        for (int k = 1; k <= piles[i - 1].size(); ++k) {
          int w = k, v = pre[k];
          if (j >= w)
            f[j] = max(f[j], f[j - w] + v);
          else
            break;
        }
      }
    }
    return f[k];
  }
};