选择哪种算法才能满足解决问题呢

Question

一道算法题，考完之后不知道该怎么优化，应该是从贪心的角度，但我从回溯去做了，结果算法复杂度过高。

题目

某石油公司需要向A、B两地运输石油。两地的需求量不同，而一辆车只能装载一定量的石油。经过计算A地需要a辆车，B地需要b辆车运输才能满足需求。现在一共有n辆车分布在各地，每辆车前往A、B两地运输石油均可以获得一定不等的利润。

现在请你安排a辆车前往A地，b辆车前往B地运输石油，使得在满足A、B两地石油需求的前提下，获得最大的利润。每辆车只能前往一地运输石油。

输入条件

输入第一行包含三个整数n，a，b，分别表示公司的车辆数量和A，B两地车辆所需数量,保证a+b<=n。(1<=n<=1000) 接下来有n行，每行两个正整数x，y，分别表示该车完成A地任务的利润和B地任务的利润。

编程

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

    private static int money = 0;

    public static int solution(int n, int a, int b, ArrayList<ArrayList<Integer>> vector){
        int result = 0;

        // TODO: 请在此编写代码
        reverse(n, 0, 2, 0, 2, 0, 0, vector);


        return money;
    }
    private static void reverse(int n, int index, int aSize, int aCount, int bSize, int bCount, int curMoney, ArrayList<ArrayList<Integer>> vector) {

        if (aCount > aSize || bCount > bSize) return;

        if (aCount == aSize && bCount == bSize && curMoney > money) {
            money = curMoney;
        }

        for(int i = index; i < n && aCount < aSize && bCount < bSize; i++) {
            reverse(n, i + 1, aSize, aCount + 1, bSize, bCount, curMoney + vector.get(index).get(0), vector);
            reverse(n, i + 1, aSize, aCount, bSize, bCount + 1, curMoney + vector.get(index).get(1), vector);
        }
    }
}

我写一个例子吧：

输出仅包含一个整数，表示最大的利润值。

示例
输入：
4 2 2
4 6
2 7
10 3
8 5

输出：
31

Answer 1

该回答引用ChatGPT

下面是从贪心的角度出发实现的Java代码：

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static class Car {
        int id; // 车辆编号
        int profitA; // 完成A地任务的利润
        int profitB; // 完成B地任务的利润
        public Car(int id, int profitA, int profitB) {
            this.id = id;
            this.profitA = profitA;
            this.profitB = profitB;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        Car[] cars = new Car[n];
        for (int i = 0; i < n; i++) {
            int profitA = in.nextInt();
            int profitB = in.nextInt();
            cars[i] = new Car(i, profitA, profitB);
        }
        // 按照完成A地任务和B地任务的利润之和从大到小排序
        Arrays.sort(cars, new Comparator<Car>() {
            @Override
            public int compare(Car o1, Car o2) {
                int sum1 = o1.profitA + o1.profitB;
                int sum2 = o2.profitA + o2.profitB;
                return sum2 - sum1;
            }
        });
        int countA = 0, countB = 0;
        int sumProfit = 0;
        for (Car car : cars) {
            if (countA < a && countB < b) {
                // 优先选取完成A地任务和B地任务的利润之和更大的车辆
                if (car.profitA > car.profitB) {
                    countA++;
                    sumProfit += car.profitA;
                } else {
                    countB++;
                    sumProfit += car.profitB;
                }
            } else if (countA < a) {
                countA++;
                sumProfit += car.profitA;
            } else if (countB < b) {
                countB++;
                sumProfit += car.profitB;
            } else {
                break;
            }
        }
        System.out.println(sumProfit);
    }
}