嗝屁小孩纸 2023-02-26 11:01 采纳率: 80.8%
浏览 34
已结题

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

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

题目

某石油公司需要向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
  • 写回答

3条回答 默认 最新

  • CodeBytes 2023-02-26 11:18
    关注

    该回答引用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);
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月13日
  • 已采纳回答 3月5日
  • 修改了问题 2月26日
  • 创建了问题 2月26日

悬赏问题

  • ¥15 大家帮我看看为什么错了
  • ¥15 unity互动琴弦抖动效果
  • ¥15 做了个的二极管反向饱和电流测量电路,但是测试达不到效果
  • ¥15 nginx无证书访问https失败
  • ¥15 树莓派启动AP热点传入数据
  • ¥15 multisim中关于74ls192n和DSWPK开关的问题(相关搜索:计数器)
  • ¥15 在误装Windows server2019 后如何利用Windows.old恢复?
  • ¥20 代码实现状态连接包过滤防火墙的设计与实现
  • ¥15 vscode的红色箭头爆红和has no default export报错
  • ¥15 关于#sql#的问题:#情况描述 在用vs对项目进行调试时,出现找不到网络路径,然后查看SQL配置工具,发现SQL服务显示远程调用过程失败(相关搜索:防火墙)