60ptsMLE求调
查看原帖
60ptsMLE求调
1037554
hetao5422877楼主2024/10/4 19:17

各位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;
}
2024/10/4 19:17
加载中...