题解 | 云服务器资源优化

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

struct State {
    int value;      // 总价值
    int power;      // 总功耗
    int count;      // 物品数量
    vector<int> items; // 选择的物品编号
};

// 比较函数：根据择优规则比较两个状态
bool isBetter(const State& a, const State& b) {
    // 规则2：价值高的更好
    if (a.value != b.value) {
        return a.value > b.value;
    }
    // 规则3：价值相同时，功耗小的更好
    if (a.power != b.power) {
        return a.power < b.power;
    }
    // 规则4：价值功耗都相同时，物品数量少的更好
    return a.count < b.count;
}

int main() {
    int n, K;
    cin >> n >> K;
    vector<int> c(n + 1), v(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> v[i];
    }

    // DP数组：dp[j] 表示容量为j时的最优状态
    vector<State> dp(K + 1, {0, 0, 0, {}});

    for (int i = 1; i <= n; i++) {
        // 倒序遍历，确保每个物品只选一次
        for (int j = K; j >= c[i]; j--) {
            State& current = dp[j];
            State& prev = dp[j - c[i]];
            
            // 选择当前物品后的新状态
            State new_state = {
                prev.value + v[i],
                prev.power + c[i],
                prev.count + 1,
                prev.items  // 复制之前的物品列表
            };
            new_state.items.push_back(i);  // 添加当前物品
            
            // 根据择优规则判断是否更新
            if (isBetter(new_state, current)) {
                dp[j] = new_state;
            }
        }
    }

    State result = dp[K];
    // 规则1：如果没有任何组合满足功耗预算，输出-1
    if ( result.value == 0) {
        cout << -1 << endl;
        return 0;
    }
    
    // 输出选择的物品编号（按输入顺序，即编号升序）
    sort(result.items.begin(), result.items.end());
    for (int i = 0; i < result.items.size(); i++) {
        if (i > 0) cout << " ";
        cout << result.items[i];
    }
    cout << endl;

    return 0;
}