解题思路

给出 n 辆车，每辆车有电池容量 cap[i] 与续航里程 rng[i]，总容量上限为 K。要求在总容量不超过 K 的前提下：

1. 总续航里程最大；
2. 若有并列，取总容量更小；
3. 若仍并列，取车辆数量更少； 并输出所选车辆的编号（升序）。若无法选择任何车辆则输出 -1。

这是标准的 0/1 背包 问题的变体。设 dp[i][w] 表示只考虑前 i 辆车、容量上限为 w 时的最优解三元组 (总续航, 总容量, 车辆数)，转移：

• 不选第 i 辆：dp[i-1][w]
• 选第 i 辆（若 w>=cap[i]）：dp[i-1][w-cap[i]] 再加上第 i 辆的属性

三元组比较规则（自定义“更优”）：

1. 总续航更大优先；
2. 若续航相同，总容量更小优先；
3. 若仍相同，车辆数更少优先。

用 take[i][w] 记录是否选择第 i 辆，最终从 dp[n][K] 反推路径并输出编号升序。

输入格式按样例：第一行 n，第二行 K，第三行 n 个容量，第四行 n 个续航。

复杂度分析

• 时间复杂度：O(n*K)，其中 n ≤ 50，K ≤ 1000，可行。
• 空间复杂度：O(n*K)，存储三个整型表与选择表，同样可行。

代码实现

Python

# 题面功能函数：求解并返回选择的车辆编号（升序），若无则返回空列表
def choose_cars(cap, rng, K):
    n = len(cap)
    # dp 三个维度：总续航、总容量、车辆数
    val = [[0]*(K+1) for _ in range(n+1)]
    wt  = [[0]*(K+1) for _ in range(n+1)]
    cnt = [[0]*(K+1) for _ in range(n+1)]
    take = [[False]*(K+1) for _ in range(n+1)]

    # 比较 (v1,w1,c1) 是否比 (v2,w2,c2) 更优
    def better(v1, w1, c1, v2, w2, c2):
        if v1 != v2: return v1 > v2
        if w1 != w2: return w1 < w2
        return c1 < c2

    for i in range(1, n+1):
        ci, vi = cap[i-1], rng[i-1]
        for w in range(0, K+1):
            # 不选
            v0, w0, c0 = val[i-1][w], wt[i-1][w], cnt[i-1][w]
            best_v, best_w, best_c = v0, w0, c0
            # 选
            if w >= ci:
                v2 = val[i-1][w-ci] + vi
                w2 = wt[i-1][w-ci] + ci
                c2 = cnt[i-1][w-ci] + 1
                if better(v2, w2, c2, best_v, best_w, best_c):
                    best_v, best_w, best_c = v2, w2, c2
                    take[i][w] = True
                else:
                    take[i][w] = False
            else:
                take[i][w] = False
            val[i][w], wt[i][w], cnt[i][w] = best_v, best_w, best_c

    # 若未选中任何车辆，则输出 -1
    if cnt[n][K] == 0:
        return []

    # 反推路径
    ans = []
    w = K
    for i in range(n, 0, -1):
        if take[i][w]:
            ans.append(i)     # 车辆编号从 1 开始
            w -= cap[i-1]
    ans.reverse()
    return ans

# 主函数：读入、调用、输出
if __name__ == "__main__":
    import sys
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        exit(0)
    n, K = data[0], data[1]
    cap = data[2:2+n]
    rng = data[2+n:2+2*n]
    res = choose_cars(cap, rng, K)
    if not res:
        print(-1)
    else:
        print(" ".join(map(str, res)))

Java

import java.util.*;

// ACM 风格，类名为 Main
public class Main {

    // 题面功能函数：返回选择的车辆编号（升序），若无则返回空数组
    public static List<Integer> chooseCars(int[] cap, int[] rng, int K) {
        int n = cap.length;
        int[][] val = new int[n + 1][K + 1]; // 总续航
        int[][] wt  = new int[n + 1][K + 1]; // 总容量
        int[][] cnt = new int[n + 1][K + 1]; // 车辆数
        boolean[][] take = new boolean[n + 1][K + 1];

        // 比较 (v1,w1,c1) 是否优于 (v2,w2,c2)
        java.util.function.Predicate<int[]> dummy = x -> true; // 仅为避免警告
        for (int i = 1; i <= n; i++) {
            int ci = cap[i - 1], vi = rng[i - 1];
            for (int w = 0; w <= K; w++) {
                // 不选
                int bv = val[i - 1][w], bw = wt[i - 1][w], bc = cnt[i - 1][w];
                boolean tk = false;
                // 选
                if (w >= ci) {
                    int v2 = val[i - 1][w - ci] + vi;
                    int w2 = wt[i - 1][w - ci] + ci;
                    int c2 = cnt[i - 1][w - ci] + 1;
                    if (better(v2, w2, c2, bv, bw, bc)) {
                        bv = v2; bw = w2; bc = c2; tk = true;
                    }
                }
                val[i][w] = bv; wt[i][w] = bw; cnt[i][w] = bc; take[i][w] = tk;
            }
        }

        if (cnt[n][K] == 0) return new ArrayList<>(); // 无可选车辆

        // 反推路径
        List<Integer> ans = new ArrayList<>();
        int w = K;
        for (int i = n; i >= 1; i--) {
            if (take[i][w]) {
                ans.add(i); // 编号从 1 开始
                w -= cap[i - 1];
            }
        }
        Collections.reverse(ans);
        return ans;
    }

    // 自定义比较：续航大优先；续航相同容量小优先；再者车辆数少优先
    private static boolean better(int v1, int w1, int c1, int v2, int w2, int c2) {
        if (v1 != v2) return v1 > v2;
        if (w1 != w2) return w1 < w2;
        return c1 < c2;
    }

    // 主函数：读入、调用、输出
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        int K = sc.nextInt();
        int[] cap = new int[n];
        int[] rng = new int[n];
        for (int i = 0; i < n; i++) cap[i] = sc.nextInt(); // 第三行：容量
        for (int i = 0; i < n; i++) rng[i] = sc.nextInt(); // 第四行：续航
        List<Integer> res = chooseCars(cap, rng, K);
        if (res.isEmpty()) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < res.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(res.get(i));
            }
            System.out.println();
        }
    }
}

C++

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

// 题面功能函数：返回选择的车辆编号（升序），若无则返回空向量
vector<int> choose_cars(const vector<int>& cap, const vector<int>& rng, int K) {
    int n = cap.size();
    // 三个 DP 表：总续航、总容量、车辆数
    vector<vector<int>> val(n + 1, vector<int>(K + 1, 0));
    vector<vector<int>> wt (n + 1, vector<int>(K + 1, 0));
    vector<vector<int>> cnt(n + 1, vector<int>(K + 1, 0));
    vector<vector<char>> take(n + 1, vector<char>(K + 1, 0));

    auto better = [](int v1, int w1, int c1, int v2, int w2, int c2)->bool{
        if (v1 != v2) return v1 > v2;
        if (w1 != w2) return w1 < w2;
        return c1 < c2;
    };

    for (int i = 1; i <= n; ++i) {
        int ci = cap[i - 1], vi = rng[i - 1];
        for (int w = 0; w <= K; ++w) {
            // 不选
            int bv = val[i - 1][w], bw = wt[i - 1][w], bc = cnt[i - 1][w];
            char tk = 0;
            // 选
            if (w >= ci) {
                int v2 = val[i - 1][w - ci] + vi;
                int w2 = wt[i - 1][w - ci] + ci;
                int c2 = cnt[i - 1][w - ci] + 1;
                if (better(v2, w2, c2, bv, bw, bc)) {
                    bv = v2; bw = w2; bc = c2; tk = 1;
                }
            }
            val[i][w] = bv; wt[i][w] = bw; cnt[i][w] = bc; take[i][w] = tk;
        }
    }

    if (cnt[n][K] == 0) return {}; // 无可选车辆

    // 反推路径
    vector<int> ans;
    int w = K;
    for (int i = n; i >= 1; --i) {
        if (take[i][w]) {
            ans.push_back(i); // 编号从 1 开始
            w -= cap[i - 1];
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if (!(cin >> n)) return 0;
    cin >> K;
    vector<int> cap(n), rng(n);
    for (int i = 0; i < n; ++i) cin >> cap[i]; // 第三行：容量
    for (int i = 0; i < n; ++i) cin >> rng[i]; // 第四行：续航
    vector<int> res = choose_cars(cap, rng, K);
    if (res.empty()) {
        cout << -1 << "\n";
    } else {
        for (size_t i = 0; i < res.size(); ++i) {
            if (i) cout << ' ';
            cout << res[i];
        }
        cout << "\n";
    }
    return 0;
}

题目内容

有从 $1$ 到 $n$ 按序编号的 $n$ 辆纯电的新能源汽车，给定一个总的电池容量 $k$ ，请根据每辆新能源汽车的电油容量和续航里程情况，选取出对应的新能源汽车的组合，满足所选择的组合内的新能源汽车的电油容量总和不大于 $k$ ，总续航里程最高。

输入描述

第一行输入为整数 $n$ ，表示新能源汽车数量，范围为 $1$ ~ $50$ ;

第二行输入为整数 $k$ ，表示给定的总的电池容量，范围为 $1$ ~ $1000$ ;

接下来的 $n$ 行输入，按照 $1$ 到 $n$ 按序编号顺序，逐行表示对应编号的新能源汽车的电池容量和续航里程，以空格分隔;

电池容量范围为 $1$ ~ $100$，续航里程范围为 $1$ ~ $1000$ 。

输出描述

按照编码从小到大输出所选组合中的新能源汽车编号，编号间以空格隔开。

注意:

$1$、如果没有满足要求的组合，输出 $-1$ 。

$2$、如果存在多个满足条件的组合均达到最高里程，则取总电量最少的组合输出。

在上述前提下，若存在多个组合均满足最少总电量，则取汽车数量最少的组合输出。

在上述前提下，题目可保证仅有一组组合。

样例1

输入

1
80
100
300

输出

-1

说明

该用例中不存在电量不大于 $80$ 的组合，因此返回 $-1$

样例2

输入

5
80
30 45 15 15 80
400 470 200 200 870

输出

1 2

说明

一共 $5$ 辆车，电油容量分别为 $30、45、15、15、80$ ，续航里程分别为 $400、470、200、200、870$ ，总电量要求不大于 $80$ 。

对应如下表

总电量不大于 $80$ 的车辆组合可以是：$(1)、(2)、(3)、(4)、(5)、(1,2)、(1,3)、(1,4)、(1,3,4)、(2,3)、(2,4)、(2,3,4)、(3,4)$

对应的总电量依次为:

$30、45、15、15、80、75、45、45、60、60、60、75、30$

对应的总续航里程依次为:

$400、470、200、200、870、870、600、600、800，670、670、870、400$

由上可知，满足条件的最高续航里程为 $870$ ，分别为组合 $(5)、(1,2)、(2,3,4)$

在续航里程相同的情况下，取电量最小的组合，分别为 $(1,2)、(2,3,4)$

在电量相同的情况下，取汽车数量最小的组合，为 $(1,2)$

因此最终输出为

$1$ $2$

样例3

输入

4
80
30 45 50 60
400 470 450 600

输出

1 2

说明

一共 $4$ 辆车，电池容量分别为 $30、45、50、60$，续航里程分别为 $400、470、450、600$，总电量要求不大于 $80$ 。

总电量不大于 $80$ 的车辆组合可以是 $1$ (总电量 $30$ )、$1$ 和 $2$ (总电量 $75$ )、$1$ 和 $3$ (总电量 $80$ )、$2$ (总电量 $45$ )、$3$(总电量 $50$ )、$4$ (总电量 $60$ )，总续航里程分别为 $400,870,850,470,450,600$ .

因此最长续航里程为 $870$ ，对应的组合为 $1$ 和 $2$ 。

最终输出

$1$ $2$