哪里会有人喜欢孤独，只不过是不喜欢失望。

前言

最近看了下《算法图解》确实给自己不少启发，感觉自己看世界都多了一个角度、多了一分透彻，就连玩游戏的时候也是如此。不过书中的代码示例都是用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;/*** @author guqueyue* @Date 2020/8/24* 韩信买皮肤问题**/
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);}/*** 在控制台打印出购买策略* @param buy   购买集合* @param 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 + " ");});}/*** 初始化变量，通过减去余额优惠卷等计算出实际需要购买的点券数量* @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;}/*** 根据贪心算法求出购买点券的策略* @param money    实际需要购买的点券数量* @return*/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;}/*** 找到可以购买的点券数组中数额最大的但是不超过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;}
}

控制台输出结果得：

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

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