有目录，不迷路

• 前言
• 言归正传
• 贪心算法

前言

最近看了下《算法图解》确实给自己不少启发，感觉自己看世界都多了一个角度、多了一分透彻，就连玩游戏的时候也是如此。不过书中的代码示例都是用python来实现的，而本人是以java为主攻方向。所以，就阅读体验上来讲，未免让我有些不快。为此，我特意将书中的python代码都一一翻译成了Java代码。链接如下：

肝了几万字，送给看了《算法图解》却是主攻Java的你和我（上篇）

肝了几万字，送给看了《算法图解》却是主攻Java的你和我（下篇）

言归正传

下面开始描述问题：

本人平时比较喜欢玩王者荣耀，最近玩韩信比较多，就想买一个韩信街头霸王的皮肤。

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

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

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

贪心算法

这个时候，可能大都会想到两种算法：动态规划算法和贪心算法。
这里容我偷个懒，采用简单易行的贪心算法。至于动态规划算法的解法感兴趣的小伙伴们可以自己试试看。至于贪心算法的核心理念，之前的博客也提到过：

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

代码如下，注释还是蛮详细的：

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


public class SkinBuy {

    // 可以购买的点券数量
    static int[] coupon = {10, 60, 180, 300, 680, 1180, 1980};

    public static void main(String[] args) {

        // 初始化变量，通过减去余额优惠卷等计算出实际需要购买的点券数量
        int money = getMoney();

        // 根据贪心算法得到如何购买的点券集合
        List<Integer> buy = getHowBuy(money);
        // 输出购买策略
        print(buy, money);

    }

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

    
    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;
    }

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

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

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

        return buy;
    }

    
    private static int maxCoupon(int money) {

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

        return maxCoupon;
    }
}

控制台输出结果得：

哼哼，完美！经过这么一番折腾，买皮肤都变得心安理得了：

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