解题思路

第一问就是简单的01背包问题，这里不多赘述，有不明白的自己去找资料吧。

关键是第二问，问背包恰好装满的情况下，最多能装价值多少的物品。这里的恰好装满是关键。

为了避免不必要的空间浪费，我这里使用map进行处理，其中map的任意一个键值对[key, val]表示正好装满体积为key的空间的最大价值为val。

map的底层是红黑树，它本身是一个有序的容器，增删改查的时间复杂度都在O(logn)。

我们让map的key从大到小排列，这样方便后续的状态转移。具体做法是：

1、初始化map[0] = 0，即体积为0时价值为0。

2、对于每一件物品的v和w，我们遍历整个map的所有键值对[key, val]，若key + v <= V，有状态转移方程

map[key + v] = max(map[key + v], val + w)。

下面贴出完整代码。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    int n, V, v, w;
    cin >> n >> V;
    vector<int> dp(V + 1, 0);
    map<int, int, greater<>> mp;
    mp[0] = 0;
    for (int i = 0; i < n; ++i) {
        cin >> v >> w;
        for (int j = V; j >= v; --j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
        for (auto &[key, val] : mp) {
            if (key + v <= V) mp[key + v] = max(mp[key + v], val + w);
        }
    }
    cout << dp[V] << endl;
    cout << mp[V];
}