云服务器资源优化

题目描述

作为云计算工程师，需要从 n 个待选服务中选择最优组合部署到物理服务器。在功耗预算 W 的限制下，实现最大计算价值。

输出选中服务的编号（1-indexed），按升序排列。优先级规则：

1. 无法满足预算（没有任何非空子集的总功耗 <= W）则输出 -1
2. 相同最高价值时，选总功耗最小的组合
3. 仍有多个时，选服务数量最少的组合
4. 题目保证最终只有唯一最优解

思路

本题是经典的 0/1 背包问题的变体，难点在于需要处理多级优先的选择规则，以及最终输出具体方案而非仅输出最优值。

状态设计

定义 dp[j] 为容量为 j 时的最优状态，每个状态包含三个维度：

• 总价值 val（越大越好）
• 总功耗 wt（价值相同时，越小越好）
• 服务数量 cnt（价值和功耗都相同时，越小越好）

对于状态比较，将其编码为元组 (val, -wt, -cnt) 取最大值，即可同时满足三级优先规则。

转移

标准 0/1 背包逆序枚举容量：

$$

其中 max 按照三元组的字典序比较。

方案回溯

使用 choice[i][j] 记录处理第 i 个物品、容量为 j 时是否选择了该物品。从 dp[W] 出发，逆序扫描物品即可还原方案。

复杂度分析

• 时间复杂度：
• 空间复杂度：（主要是 choice 数组）

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, W;
    scanf("%d%d", &n, &W);
    vector<int> w(n), v(n);
    for(int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);

    struct State {
        long long val;
        int wt, cnt;
        bool operator<(const State& o) const {
            if(val != o.val) return val < o.val;
            if(wt != o.wt) return wt > o.wt;
            return cnt > o.cnt;
        }
    };

    vector<State> dp(W + 1, {0, 0, 0});
    vector<vector<bool>> choice(n, vector<bool>(W + 1, false));

    for(int i = 0; i < n; i++){
        for(int j = W; j >= w[i]; j--){
            State take = {dp[j - w[i]].val + v[i], dp[j - w[i]].wt + w[i], dp[j - w[i]].cnt + 1};
            if(dp[j] < take){
                dp[j] = take;
                choice[i][j] = true;
            }
        }
    }

    if(dp[W].val == 0){
        printf("-1\n");
        return 0;
    }

    vector<int> selected;
    int j = W;
    for(int i = n - 1; i >= 0; i--){
        if(choice[i][j]){
            selected.push_back(i + 1);
            j -= w[i];
        }
    }
    sort(selected.begin(), selected.end());
    for(int i = 0; i < (int)selected.size(); i++){
        if(i) printf(" ");
        printf("%d", selected[i]);
    }
    printf("\n");
    return 0;
}

Java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int W = sc.nextInt();
        int[] w = new int[n], v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        long[] dpVal = new long[W + 1];
        int[] dpWt = new int[W + 1];
        int[] dpCnt = new int[W + 1];
        boolean[][] choice = new boolean[n][W + 1];

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= w[i]; j--) {
                long nv = dpVal[j - w[i]] + v[i];
                int nw = dpWt[j - w[i]] + w[i];
                int nc = dpCnt[j - w[i]] + 1;
                if (better(nv, nw, nc, dpVal[j], dpWt[j], dpCnt[j])) {
                    dpVal[j] = nv;
                    dpWt[j] = nw;
                    dpCnt[j] = nc;
                    choice[i][j] = true;
                }
            }
        }

        if (dpVal[W] == 0) {
            System.out.println(-1);
            return;
        }

        ArrayList<Integer> selected = new ArrayList<>();
        int j = W;
        for (int i = n - 1; i >= 0; i--) {
            if (choice[i][j]) {
                selected.add(i + 1);
                j -= w[i];
            }
        }
        Collections.sort(selected);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < selected.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(selected.get(i));
        }
        System.out.println(sb);
    }

    static boolean better(long v1, int w1, int c1, long v2, int w2, int c2) {
        if (v1 != v2) return v1 > v2;
        if (w1 != w2) return w1 < w2;
        return c1 < c2;
    }
}

Python3

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    W = int(input())
    items = []
    for _ in range(n):
        a, b = map(int, input().split())
        items.append((a, b))

    # dp[j] = (val, -wt, -cnt)，取最大值即满足三级优先
    dp = [(0, 0, 0)] * (W + 1)
    choice = [[False] * (W + 1) for _ in range(n)]

    for i in range(n):
        wi, vi = items[i]
        for j in range(W, wi - 1, -1):
            pv, pw, pc = dp[j - wi]
            nv, nw, nc = pv + vi, pw - wi, pc - 1
            if (nv, nw, nc) > dp[j]:
                dp[j] = (nv, nw, nc)
                choice[i][j] = True

    if dp[W][0] == 0:
        print(-1)
        return

    selected = []
    j = W
    for i in range(n - 1, -1, -1):
        if choice[i][j]:
            selected.append(i + 1)
            j -= items[i][0]

    selected.sort()
    print(' '.join(map(str, selected)))

main()

JavaScript

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const n = parseInt(lines[idx++]);
    const W = parseInt(lines[idx++]);
    const w = [], v = [];
    for (let i = 0; i < n; i++) {
        const parts = lines[idx++].split(/\s+/).map(Number);
        w.push(parts[0]);
        v.push(parts[1]);
    }

    const dpVal = new Array(W + 1).fill(0);
    const dpWt = new Array(W + 1).fill(0);
    const dpCnt = new Array(W + 1).fill(0);
    const choice = Array.from({length: n}, () => new Array(W + 1).fill(false));

    for (let i = 0; i < n; i++) {
        for (let j = W; j >= w[i]; j--) {
            const nv = dpVal[j - w[i]] + v[i];
            const nw = dpWt[j - w[i]] + w[i];
            const nc = dpCnt[j - w[i]] + 1;
            if (nv > dpVal[j] || (nv === dpVal[j] && nw < dpWt[j]) ||
                (nv === dpVal[j] && nw === dpWt[j] && nc < dpCnt[j])) {
                dpVal[j] = nv;
                dpWt[j] = nw;
                dpCnt[j] = nc;
                choice[i][j] = true;
            }
        }
    }

    if (dpVal[W] === 0) {
        console.log(-1);
        return;
    }

    const selected = [];
    let j = W;
    for (let i = n - 1; i >= 0; i--) {
        if (choice[i][j]) {
            selected.push(i + 1);
            j -= w[i];
        }
    }
    selected.sort((a, b) => a - b);
    console.log(selected.join(' '));
});