解题思路

本题是一个变形的背包问题：每个包裹可以选择两种“花费”（燃料），其中一种会额外消耗 1 张通行证。目标是先最大化派送包裹数，在此基础上最小化燃料消耗，并满足燃料 ≤ X、通行证 ≤ Y。

算法：动态规划（DP，二元约束下的最优化-可行性分离）

• 设计状态： 设 dp[j][k] 表示在处理若干包裹后，恰好派送 j 个包裹、使用 k 张通行证时的最小燃料。 初始化：dp[0][0] = 0，其余为正无穷。

• 转移（对每个包裹的常规/虫洞两种选择）：

  • 常规派送（不耗通行证）： dp[j+1][k] = min(dp[j+1][k], dp[j][k] + a_i)
  • 虫洞派送（耗 1 张通行证）： 若 k+1 ≤ Y， dp[j+1][k+1] = min(dp[j+1][k+1], dp[j][k] + b_i)

• 为避免同一轮中重复使用更新后的值，j 必须从大到小循环（k 也可从大到小循环）。

• 扫描答案：从 j = N..0 递减，找到满足 min_k dp[j][k] ≤ X 的最大 j；对应最小燃料为该 j 下所有 k 中的最小 dp[j][k]。

该思路将“最大化数量、次级最小化燃料”的字典序目标自然体现在状态与转移里：先按 j 优先级搜索可行解，再在同一 j 内取最小燃料。

复杂度分析

• 状态规模：(N+1) × (Y+1)。
• 每个包裹进行一次两种转移，内层遍历 j ∈ [0..i] 与 k ∈ [0..Y]，因此总时间复杂度 O(N × N × Y)（j 上界随已处理包裹数增长，整体 ≤ N^2 Y）。在数据范围 N ≤ 100, Y < 50 下约 50 万级别，完全可行。
• 空间复杂度：O(N × Y)。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：在燃料和通行证限制下，优先最大化派送包裹数，其次最小化燃料
# 算法：dp[j][k] = 派送j个、用k张通行证的最小燃料；每个包裹两种转移，j与k倒序更新

import sys

INF = 10**9

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    N = int(next(it)); X = int(next(it)); Y = int(next(it))
    items = []
    for _ in range(N):
        a = int(next(it))  # 常规燃料
        b = int(next(it))  # 虫洞燃料（耗1张票）
        items.append((a, b))

    # dp[j][k] = 最小燃料
    dp = [[INF] * (Y + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for a, b in items:
        # j从大到小，防止同一物品被重复计入
        for j in range(N - 1, -1, -1):
            # k从大到小，安全避免本轮污染
            for k in range(Y, -1, -1):
                if dp[j][k] == INF:
                    continue
                # 常规派送，不耗通行证
                if dp[j][k] + a < dp[j + 1][k]:
                    dp[j + 1][k] = dp[j][k] + a
                # 虫洞派送，耗1张通行证
                if k + 1 <= Y and dp[j][k] + b < dp[j + 1][k + 1]:
                    dp[j + 1][k + 1] = dp[j][k] + b

    # 找到最大可派送数与对应最小燃料
    best_cnt = 0
    best_fuel = 0
    for j in range(N, -1, -1):
        cur = min(dp[j])  # 在所有通行证使用量中取最小燃料
        if cur <= X:
            best_cnt = j
            best_fuel = cur
            break

    print(best_cnt, best_fuel)

if __name__ == "__main__":
    solve()

Java

// 题意：在燃料与通行证限制下，先最大化派送数量，再最小化燃料
// 算法：dp[j][k] 表示派送 j 个、用 k 张通行证的最小燃料；每个包裹两种选择，j、k 倒序更新

import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), X = sc.nextInt(), Y = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt(); // 常规燃料
            B[i] = sc.nextInt(); // 虫洞燃料（耗1张通行证）
        }

        // dp[j][k] = 最小燃料
        int[][] dp = new int[N + 1][Y + 1];
        for (int i = 0; i <= N; i++) Arrays.fill(dp[i], INF);
        dp[0][0] = 0;

        // 逐个包裹处理
        for (int i = 0; i < N; i++) {
            int a = A[i], b = B[i];
            for (int j = N - 1; j >= 0; j--) {
                for (int k = Y; k >= 0; k--) {
                    if (dp[j][k] == INF) continue;
                    // 常规派送
                    if (dp[j][k] + a < dp[j + 1][k]) {
                        dp[j + 1][k] = dp[j][k] + a;
                    }
                    // 虫洞派送（多用1张通行证）
                    if (k + 1 <= Y && dp[j][k] + b < dp[j + 1][k + 1]) {
                        dp[j + 1][k + 1] = dp[j][k] + b;
                    }
                }
            }
        }

        int bestCnt = 0, bestFuel = 0;
        for (int j = N; j >= 0; j--) {
            int cur = INF;
            for (int k = 0; k <= Y; k++) cur = Math.min(cur, dp[j][k]);
            if (cur <= X) {
                bestCnt = j;
                bestFuel = cur;
                break;
            }
        }

        System.out.println(bestCnt + " " + bestFuel);
    }
}

C++

// 题意：在燃料与通行证约束下，优先最大化派送包裹数，并使燃料最小
// 算法：dp[j][k] = 派送j个、用k张通行证的最小燃料；对每个包裹进行两种转移，j/k倒序

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

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, X, Y;
    if (!(cin >> N >> X >> Y)) return 0;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i]; // A:常规燃料，B:虫洞燃料（耗1张通行证）
    }

    // dp[j][k] = 最小燃料
    vector<vector<int>> dp(N + 1, vector<int>(Y + 1, INF));
    dp[0][0] = 0;

    for (int i = 0; i < N; ++i) {
        int a = A[i], b = B[i];
        for (int j = N - 1; j >= 0; --j) {
            for (int k = Y; k >= 0; --k) {
                if (dp[j][k] == INF) continue;
                // 常规派送
                dp[j + 1][k] = min(dp[j + 1][k], dp[j][k] + a);
                // 虫洞派送（多用1张通行证）
                if (k + 1 <= Y) {
                    dp[j + 1][k + 1] = min(dp[j + 1][k + 1], dp[j][k] + b);
                }
            }
        }
    }

    int bestCnt = 0, bestFuel = 0;
    for (int j = N; j >= 0; --j) {
        int cur = INF;
        for (int k = 0; k <= Y; ++k) cur = min(cur, dp[j][k]);
        if (cur <= X) {
            bestCnt = j;
            bestFuel = cur;
            break;
        }
    }

    cout << bestCnt << " " << bestFuel << "\n";
    return 0;
}

题目内容

星际快递公司有 $N$ 个包裹需要派送，每个包裹有两种派送方式!

1、常规派送(消耗较多燃料)

2、虫洞派送(使用一个虫洞通行证，可以以消耗较少燃料的情况下完成派送)

当前快递飞船携带了 $X$ 单位的燃料和 $Y$ 张虫洞通行证。

星际快递公司想要计算，在优先派送尽可能多包裹的情况下，最小的燃料消耗是多少，请你帮助他们计算一下。

输入描述

第一行三个整数 $N,X,Y$ ，分别表示包裹数量，携带燃料量以及通行证数量。

接下来 $N$ 行，每行两个整数，表示各个包裹常规派送和虫洞派送分别需要的燃料量

$1≤N≤100,1≤X≤5000,1≤Y<50$ ，每个包裹常规派送和虫洞派送的燃料消耗均介于 $[1,50]$ 之间

输出描述

一行，两个整数，空格分开，表示最多可派送的包裹数量及对应的最小燃料消耗。

样例1

输入

3 20 1
8 5
7 4
10 6

输出

2 12

样例2

输入

4 25 2
10 6
8 5
12 7
9 6

输出

3 20