vlambda博客
学习文章列表

贪心算法实践 | 王者荣耀购买点券最优策略

✨一起学习、成长、温情的热爱生活✨   

图丨pixabay


    

    原文链接:http://nxw.so/4iigd




下面开始描述问题:

本人平时比较喜欢玩王者荣耀,最近玩韩信比较多,打野飕飕的,虽然很坑,就想买一个韩信街头霸王的皮肤。

贪心算法实践 | 王者荣耀购买点券最优策略

但是在购买点券的过程中发现这样一个问题

贪心算法实践 | 王者荣耀购买点券最优策略

我竟然不能够随心所欲的购买点券数量,只能按照腾讯规定的数量购买点券。这应该是腾讯为了刺激用户消费所设置的规则。毕竟自己去凑点券数量也不太好计算,嫌麻烦的用户可能就会直接购买超量的点券。但是这个时候我突然就想挑战一波,拒绝超量消费(其实是穷 )。于是阐述问题试图求解:

如果我想买一个韩信街头霸王的皮肤,已知皮肤的价格为888点券,而我有50点券的优惠卷,余额为8点券,也就是说我需 要购买830点券。但是购买点券的数量又不能随心所欲,如上图所示。但是因为最小单位是1元,也就是10点券,所以我肯定可以凑的刚刚好。问:如何花最少的次数刚好买到830点券?

贪心算法

这个时候,可能大都会想到两种算法:动态规划算法和贪心算法

这里容我偷个懒,采用简单易行的贪心算法。至于动态规划算法的解法感兴趣的小伙伴们可以自己试试看。至于贪心算法的核心理念:

每一步都采取最优的做法。用专业术语来讲就是:每一步都选择局部最优解,进而希望最终获得一个全局最优解。

代码如下,注释还是蛮详细的:

package 贪心;
/*
作者     :XiangLin
创建时间 :2020/9/9 18:47
文件     :SkinBuy.java
IDE      :IntelliJ IDEA
*/


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

public class SkinBuy {
    // 可以购买的点券数量
    static int[] coupon = {106018030068011801980};

    public static void main(String[] args) {
        // 初始化变量,通过减去余额优惠卷等计算出实际需要购买的点券数量
        int money = getMoney();

        // 根据贪心算法得到如何购买的点券集合
        List<Integer> buy = getHowMoney(money);

        // 输出购买策略
        prin(buy,money);
    }

    private static void prin(List<Integer> buy, int money) {
        System.out.println("尊敬的腾讯抠门用户,您最少需要花 " + buy.size() + " 次才能刚好凑到" + money + "点券");
        System.out.println("您只需要这样购买点券:");
        buy.forEach(b->{// 遍历点券集合输出即可
            System.out.print(b + " ");
        });
    }

    /**
     * 根据贪心算法求出购买点券的策略
     * @param money    实际需要购买的点券数量
     * @return
     */


    private static List<Integer> getHowMoney(int money) {

        List<Integer> buy = new ArrayList<>();

        while (money > 0){
            // 找到可以购买的点券数组中数额最大的但是不超过money点券数
            int maxCoupon = maxCoupon(money);
            money -= maxCoupon;
            buy.add(maxCoupon);
        }

        return buy;
    }

    /**
     * 找到可以购买的点券数组中数额最大的但是不超过money点券数
     * @param money 实际需要购买的点券数量
     * @return
     */

    private static int maxCoupon(int money) {

        // 默认为10 - 最小点券购买数
        int maxCoupon = 10;
        for (int m : coupon) {
            // 有序数组才可以这样
            if (money >= m){
                maxCoupon = m;
            }
        }
        return maxCoupon;
    }

    /**
     * 初始化变量,通过减去余额优惠卷等计算出实际需要购买的点券数量
     * @return
     */

    private static int getMoney() {
        Scanner input = new Scanner(System.in);

        // 皮肤的价钱 - 888点券
        System.out.print("请输入您要购买皮肤的价格(点券):");
        int price = input.nextInt();

        // 账户余额 - 8点券
        System.out.print("请输入您的账户余额:");
        int banlance = input.nextInt();

        // 优惠卷 - 50点券
        System.out.print("请输入您的优惠卷:");
        int discount = input.nextInt();

        // 实际需要购买的点券
        int money = price - banlance - discount;
        return money;
    }

}

控制台输出结果得:

贪心算法实践 | 王者荣耀购买点券最优策略

哼哼,完美!经过这么一番折腾,买皮肤都变得心安理得了:

贪心算法实践 | 王者荣耀购买点券最优策略

升到了贵族6, 还送了一个狄仁杰的皮肤:



所有巧合的是要么是上天注定要么是一个人偷偷的在努力。

结束!

往期推荐