有目錄，不迷路
- 前言
- 言歸正傳
- 貪心演算法
前言
最近看了下《演算法圖解》確實給自己不少啟發，感覺自己看世界都多了一個角度、多了一分透徹，就連玩游戲的時候也是如此，不過書中的代碼示例都是用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， 還送了一個狄仁杰的皮膚：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1493.html
標籤：區塊鏈