This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n; // 物品的数量
int m; // 背包的体积上限
int w[N]; // 每个物品的价值
int v[N]; // 每个物品的重量，体积
/**
* 功能：深度优先搜索
* @param u 走到第u物品面前
* @param r 剩余容量r
* @return 可以获得的最大价值是多少
*/
int dfs(int u, int r) {
// 如果出界了，返回0
if (u == n + 1) return 0;
// 如果不够装下，只能放弃
if (v[u] > r) return dfs(u + 1, r);
// 如果可以装下，可以选择要、还是不要
return max(dfs(u + 1, r), dfs(u + 1, r - v[u]) + w[u]);
}
int main() {
// 物品个数与背包容量
cin >> n >> m;
// 读入每个物品的体积和价值
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// 深搜并输出结果~
printf("%d\n", dfs(1, m));
return 0;
