游游的游戏大礼包
import java.util.*; public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);long n = in.nextInt();long m = in.nextInt();long a = in.nextInt();long b = in.nextInt();long ret = 0;for(long x = 0; x <= Math.min(n / 2, m);x++) { // 枚举一号礼包的个数long y = Math.min(n - x * 2 , ( m - x ) / 2); // 枚举二号礼包的个数ret = Math.max(ret, a * x + b * y);} System.out.println(ret); }
}
我们设1号礼包X个,2号礼包Y个,那么价值的表达式就 v = a * x + b * y
可知,v这个表达式有两个变量,我们通过枚举的方法解决这类问题
比如说,先定下X的值,然后通过题目的条件确定Y的值:
X的最小值可以为0,最大值:如果全部买苹果可以买n/2份,如果全部买桃子,可以买m份,所以最大值就是 n/2 和 m 的最小值
买了X份1号,现在确定2号,苹果剩下:n-2x 桃子剩下:m-x
同理Y的范围就是min(n-2x,(m-x)/2)
枚举算法主要有以下一些缺点:
一、效率低下
- 时间复杂度高:当问题的规模较大时,需要枚举的情况数量会呈指数级增长。例如,如果要从 10 个不同的元素中选择 3 个进行排列组合,就需要枚举 A 10 3 = 10 × 9 × 8 = 720 A_{10}^3 = 10×9×8 = 720 A103=10×9×8=720 种情况。如果元素数量进一步增加或者组合的规模更大,枚举所需的时间会急剧增加。
- 空间复杂度高:在某些情况下,为了存储所有可能的枚举结果,可能需要大量的内存空间。这对于大规模问题或者资源受限的环境来说是不可行的。
二、适用性有限
- 只适用于小规模问题或有限解空间的问题:对于那些解空间非常大或者无法确定解空间大小的问题,枚举算法可能无法在合理的时间内找到解。例如,在密码破解中,如果密码长度较长且包含各种字符组合,枚举所有可能的密码将需要极其漫长的时间。
- 对于复杂问题难以直接应用:对于一些具有复杂约束条件或者动态变化的问题,枚举算法可能难以有效地进行枚举。例如,在解决旅行商问题(TSP)时,枚举所有可能的路径组合在城市数量较多时是不现实的。
三、缺乏灵活性
- 难以处理复杂的约束条件:当问题具有复杂的约束条件时,枚举算法可能需要进行大量的额外判断来确定某个枚举值是否满足所有约束条件。这不仅增加了算法的复杂性,还可能降低算法的效率。
- 不便于处理动态变化的问题:如果问题的条件在枚举过程中发生变化,枚举算法可能需要重新开始枚举或者进行复杂的调整,缺乏灵活性和适应性。