各位dalao,麻烦给下正确代码,代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int v, p; // v为价格, p为重要度
};
int main() {
int n, W;
cin >> n >> W;
vector<Item> items(n);
for (int i = 0; i < n; ++i) {
cin >> items[i].v >> items[i].p;
}
// 按照价格从小到大排序
sort(items.begin(), items.end(), [](const Item &a, const Item &b) {
return a.v < b.v;
});
// 由于价格的极差不超过3,我们可以将dp数组限制在最大4个元素
int maxImportant = 0;
for (int i = 0; i < n; ++i) {
int minPrice = items[i].v;
int maxPrice = minPrice + 3;
// dp数组用于存储当前有效状态
vector<int> dp(W + 1, 0); // dp[j] 表示花费j元的最大重要度
// 选择当前价格范围内的物品
for (int j = i; j < n && items[j].v <= maxPrice; ++j) {
int price = items[j].v;
int importance = items[j].p;
// 从后往前更新dp,避免使用同一物品多次
for (int w = W; w >= price; --w) {
dp[w] = max(dp[w], dp[w - price] + importance);
}
}
// 更新最大重要度和
maxImportant = max(maxImportant, dp[W]);
}
// 输出最大的重要度和
cout << maxImportant << endl;
return 0;
}