Java教程
PTA---贪心算法
本文主要是介绍PTA---贪心算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 7-1 装箱问题
- 7-2 月饼
- 7-4 活动选择问题
7-1 装箱问题
import java.util.Scanner;
public class Program1 {
public static void main(String[] args) {
int N;
Scanner in = new Scanner(System.in);
N = in.nextInt();
int []things = new int[N];
//最多有N个箱子
int []box = new int[N];
//记录最大所需箱子数
int maxBox = 0;
//对每个物品进行顺序装箱
for(int i = 0;i < N;i++){
//物品输入
things[i] = in.nextInt();
//存箱模拟
int index = 0;
while (box[index] + things[i] > 100 ){
index++;
}
box[index] += things[i];
System.out.println(things[i] + " " + (index + 1));
if(maxBox < index + 1){
maxBox = index + 1;
}
}
System.out.println(maxBox);
}
}
7-2 月饼
7-2 月饼 (25 分)
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。
输入格式：
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。
输出格式：
对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位
这题对java超级不友好，使用java自带的快排容易超时，而且有些还不支持。。。。。无语
Java参考代码：
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Program2 {
/**
* 解题思路：根据月饼数量和售价比值进行选择，每次选择比值最小的总收益最大
*
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt(); //月饼种类
int D = in.nextInt(); //总库存
//二维数组分别存储月饼库存，总售价
double [][]numValRate = new double[N][2];
for(int i = 0;i < N;i++){
numValRate[i][0] = in.nextDouble();
}
for(int i = 0;i < N;i++){
numValRate[i][1] = in.nextDouble();
}
//根据比值进行从小到大排序
// 下面这个排序在PTA上会超时原因不明
//Arrays.sort(numValRate, Comparator.comparingDouble(o -> ((double) o[0] / o[1])));
Arrays.sort(numValRate, new Comparator<double[]>() {
@Override
public int compare(double[] o1, double[] o2) {
if(o1[0] / o1[1] - o2[0] / o2[1] >= 0){
return 1;
}else {
return -1;
}
}
});
double sumVal = 0; //总收益
int i = 0;
while (!(D <= 0 || i >= N)){
if(D >= numValRate[i][0]){
D -= numValRate[i][0];
sumVal += numValRate[i][1];
}else {
sumVal += ((double)D / numValRate[i][0]) * numValRate[i][1];
D = 0;
}
i++;
}
System.out.printf("%.2f\n",sumVal);
}
}
可提交的C代码：
//贪心月饼问题
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *_a, const void *_b) {
double *a = (double *) (_a);
double *b = (double *) (_b);
if (a[0] / a[1] - b[0] / b[1] >= 0) {
return 1;
} else {
return -1;
}
}
int main() {
/**
* 解题思路：根据月饼数量和售价比值进行选择，每次选择比值最小的总收益最大
*
*/
int N; //月饼种类
scanf("%d", &N);
int D; //总库存
scanf("%d", &D);
//二维数组分别存储月饼库存，总售价
double numValRate[N][2];
for (int i = 0; i < N; i++) {
scanf("%lf", &numValRate[i][0]);
}
for (int i = 0; i < N; i++) {
scanf("%lf", &numValRate[i][1]);
}
qsort(numValRate, sizeof(numValRate) / sizeof(numValRate[0]), sizeof(numValRate[0]), cmp);
double sumVal = 0; //总收益
int i = 0;
while (!(D <= 0 || i >= N)) {
if (D >= numValRate[i][0]) {
D -= numValRate[i][0];
sumVal += numValRate[i][1];
} else {
sumVal += ((double) D / numValRate[i][0]) * numValRate[i][1];
D = 0;
}
i++;
}
printf("%.2f\n", sumVal);
}
##7-3 汽车加油问题 (25 分)
题目来源：王晓东《算法设计与分析》
一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。
输入格式:
第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。 第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地，汽车已加满油。 第 k+1 个加油站表示目的地。
输出格式:
输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。
import java.util.Scanner;
public class Program3 {
//贪心算法：汽油加油问题
//思路：只要剩余的油能够到达下一站就不停车，否则停车加油
static final String NoSolution = "No Solution!";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); //油箱总量
int k = in.nextInt(); //目的地数量
int []pos = new int[k + 1]; //加油站信息
for(int i = 0;i < k + 1;i++){
pos[i] = in.nextInt();
}
int minTime = 0;
int fuelTank = n;
for(int i = 0;i < k + 1;i++){
//油量充足
if(pos[i] <= fuelTank){
fuelTank -= pos[i];
}else if(pos[i] > fuelTank && fuelTank == n){
//满油箱量不足到达
minTime = -1;
break;
}else {
//加满油
fuelTank = n;
fuelTank -= pos[i];
minTime++;
}
}
if(minTime >= 0){
System.out.println(minTime);
}else {
System.out.println(NoSolution);
}
}
}
/*
7 7
1 2 3 4 5 1 6 6
*/
7-4 活动选择问题
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Program4 {
//贪心：获得选择问题
//思路：根据活动最快结束时间进行选择，开始时间为上一个活动的结束时间
//初始开始时间为0
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [][]active = new int[n][2];
for(int i = 0;i < n;i++){
active[i][0] = in.nextInt();
active[i][1] = in.nextInt();
}
//排序，根据最快结束时间进行排序,从小到大排序
Arrays.sort(active, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int times = 0; //最多活动次数
int startTime = 0;
int index = 0;
while (index < n){
if(startTime <= active[index][0]){
times++;
startTime = active[index][1];
}
index++;
}
System.out.println(times);
}
}
/*
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
*/
这篇关于PTA---贪心算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Mybatis官方生成器资料详解与应用教程11-26
-
Mybatis一级缓存资料详解与实战教程11-26
-
Mybatis一级缓存资料详解：新手快速入门11-26
-
SpringBoot3+JDK17搭建后端资料详尽教程11-26
-
Springboot单体架构搭建资料：新手入门教程11-26
-
Springboot单体架构搭建资料详解与实战教程11-26
-
Springboot框架资料：新手入门教程11-26
-
Springboot企业级开发资料入门教程11-26
-
SpringBoot企业级开发资料详解与实战教程11-26
-
Springboot微服务资料：新手入门全攻略11-26
-
SpringBoot微服务资料入门教程11-26
-
Springboot项目开发资料详解与入门指南11-26
-
SpringBoot项目开发资料详解入门教程11-26
-
SpringBoot应用的生产发布资料详解11-26
-
手写消息中间件：从零开始的指南11-26
栏目导航
