C++ 笔试刷题 Day 18：字符串压缩、TopK 与 01 背包

比较方式： 如果 first 不相等，就比较 first；如果 first 相等比较 second。 这里实现排降序：

• 如果 first 不相等，返回 a.first > b.first。
• 如果 first 相等，比较 second 返回 a.second < b.second。 这样可调用对象返回的就是 a 是否大于 b，排序即为降序。

代码实现

这里可调用对象使用 lambda 表达式实现。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;
int n, k;
typedef pair<int, int> PII;
PII arr[N];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i].second;
    for (int i = 0; i < n; i++) cin >> arr[i].first;

    sort(arr, arr + n, [](PII& a, PII& b) {
        if (a.first != b.first) return a.first > b.first;
        else return a.second < b.second;
    });

    long long a = 0, b = 0;
    for (int i = 0; i < k; i++) {
        a += arr[i].first;
        b += arr[i].second;
    }
    cout << b << ' ' << a << endl;
    return 0;
}

三、01 背包

题目解析

这是一道经典的 01 背包问题。 题目给定一个 V 表示背包的体积、n 表示物品的个数、vw 数组。 其中 vw[i][0] 表示第 i 个物品的体积、vw[i][1] 表示第 i 个物品的重量。 最后让我们返回从 n 个物品中选择体积不超过 V 的物品的最大重量。

算法思路

对于背包问题的解题思路，就是动态规划（线性 DP）。

状态表示： dp[i][j]：表示在 i 个物品中选择体积不超过 j 的物品，这些物品重量的最大值。（背包容量为 j，从 i 个物品中选择时的最大重量）。

状态转移方程： 对于 i 位置的物品，可以选择这个物品，也可以不选择。

• 如果选择 i 位置：dp[i][j] = dp[i-1][j-v[i]] + v[i]（其中 v[i] 表示 i 位置物品的重量）。
• 如果不选择 i 位置：dp[i][j] = dp[i-1][j]。

在填表时，当背包容量要大于物品 i 的体积，这时可以选择该物品（需要考虑是否选择）；如果背包容量小于物品 i 的体积，就不能选择该物品（不需要考虑）。

空间优化： 可以使用一维 dp 表来解决。 在遍历 i 时，枚举在 i 个物品中选择体积不超过 j 的物品。 对于某一个物品，不选择它时的最大重量等于此时的 dp[j]，选择它时的最大重量等于 dp[j - v[i]] + z[i]（其中 z[i] 表示 i 物品的重量）。 即 dp[j] = max(dp[j], dp[j-v[i]] + z[i])。 注意需要从右往左填表，否则就会覆盖掉之前的数据。

代码实现

二维 DP 解法：

class Solution {
public:
    int dp[1001][1001] = {0};
    int knapsack(int V, int n, vector<vector<int>>& vw) {
        // write code here
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (vw[i - 1][0] <= j) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][V];
    }
};

空间优化（一维 DP）：

class Solution {
public:
    int dp[1001] = {0};
    int knapsack(int V, int n, vector<vector<int>>& vw) {
        // write code here
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= vw[i][0]; j--) {
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }
};