本人其實内心很抵觸去埋頭刷算法題，但是有一些算法在實際業務開發中或者思想上還是值得借鑒的，是以通過這種結合實際場景的小Demo來學習和了解算法也可能是對算法提起興趣對抗枯燥的一種方法吧。
在看《劍指Offer》的時候看到回溯章節時，書中的舉一反三提到了回溯算法可以應用到像點菜這樣的場景中。例如，當客人走進餐館準備吃飯時，服務員會為客人提供一個菜單，菜單上有所有菜品的價格。如果每道菜隻點一份，那麼可人有哪些不同的點菜方法剛好将身上的錢全部用完？如果客人隻想點k道菜，那麼又有哪些不同的點菜方法可以将身上的錢全部用完？如果一道菜可以點多份呢？
結合上面多場景我們可以寫一個程式來模拟它，由于現實中不可能所有客人身上的錢都剛好能點所有的菜，是以我把上面場景中的剛好花完客人身上的錢改為在客人錢的範圍内能點多所有菜的集合，并且我隻實作前面兩種政策，即不花光身上的錢的情況下最多隻點一道菜可以有多少總政策和不花光身上的錢的情況下指定點菜的數量，并且沒到菜也是最多能點一次，至于後面的一道菜可以點多次實作類似，但意義不大，就不寫了（畢竟平時出去吃飯點菜大部分不會盯着一個菜點好幾份）。下面是代碼實作。
視訊示範
哔哩哔哩-回溯算法在點菜中的應用例子示範
使用回溯算法解決點菜問題的小Demo示範
代碼實作
為了完整的模拟，我們抽象出客人類和菜單類。
客人類
package test;
/**
* 顧客類
* @author 胡海龍<www.huhailong.vip>
*
*/
public class Customer {
/**
* 使用者名
*/
private String username;
/**
* 身上總金額 (暫時為了測試将該類型設定為整型，實際應用中應該使用高精度來修飾)
*/
private Integer amount;
//Getter and Setter
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public Integer getAmount() {
return amount;
}
public void setAmount(Integer amount) {
this.amount = amount;
}
}
菜單類
package test;
/**
* 菜單類
* @author 胡海龍<www.huhailong.vip>
*
*/
public class FoodMenu {
/**
* 菜名
*/
private String foodName;
/**
* 價格
*/
private Integer price;
//Getter and Setter
public String getFoodName() {
return foodName;
}
public void setFoodName(String foodName) {
this.foodName = foodName;
}
public Integer getPrice() {
return price;
}
public void setPrice(Integer price) {
this.price = price;
}
}
消費點單類（模拟點單）
package test;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* 結賬業務類
* @author 胡海龍<www.huhailong.vip>
*
*/
public class CheckOut {
/**
* 測試主方法
* @param args
*/
public static void main(String[] args) {
//初始化測試使用者
Customer customer = new Customer();
customer.setUsername("胡海龍");
customer.setAmount(300);
//使用一個臨時的map資料集模拟資料庫菜單表
Map<String,Integer> foodMenuMap = new HashMap<>();
foodMenuMap.put("米飯", 4);
foodMenuMap.put("魚香肉絲", 48);
foodMenuMap.put("糖醋排骨", 68);
foodMenuMap.put("京醬肉絲", 48);
foodMenuMap.put("地鍋雞", 78);
foodMenuMap.put("螞蟻上樹", 178);
foodMenuMap.put("毛氏紅燒肉", 79);
foodMenuMap.put("蒜末拍黃瓜", 12);
//初始化菜單清單
List<FoodMenu> foodMenuList = new LinkedList<>();
for(String key : foodMenuMap.keySet()) {
FoodMenu menu = new FoodMenu();
menu.setFoodName(key);
menu.setPrice(foodMenuMap.get(key));
foodMenuList.add(menu);
}
//定義結果集
List<List<FoodMenu>> result = new LinkedList<>();
makePolicy1(foodMenuList, 0, customer.getAmount(), new LinkedList<>(), result);
// makePolicy2(foodMenuList, 0, customer.getAmount(), 2, new LinkedList<>(), result);
//列印政策
printPolicy(result);
}
/**
* 政策1 每道菜最多隻點一次，在不花光身上所有錢的情況下有哪些點菜的政策
* @param foodMenuList 菜單集合
* @param index 菜單索引
* @param total 顧客身上總錢數
* @param tempList 臨時存儲集合
* @param result 政策結果集合
*/
private static void makePolicy1(List<FoodMenu> foodMenuList, int index, int total, LinkedList<FoodMenu> tempList, List<List<FoodMenu>> result) {
int sum = tempList.stream().mapToInt(FoodMenu::getPrice).sum();
if(index==foodMenuList.size()&&sum<=total) {
result.add(new LinkedList<>(tempList));
}else if(index < foodMenuList.size()) {
makePolicy1(foodMenuList, index+1, total, tempList, result);
tempList.add(foodMenuList.get(index));
makePolicy1(foodMenuList, index+1, total, tempList, result);
tempList.removeLast();
}
}
/**
* 政策2 每道菜最多隻點一次，并且顧客指定點k道菜，在不花光身上所有錢的情況下有哪些點菜的政策
* @param foodMenuList 菜單集合
* @param index 菜單索引
* @param total 顧客身上總錢數
* @param k 指定菜的數量
* @param tempList 臨時存儲集合
* @param result 政策結果集合
*/
private static void makePolicy2(List<FoodMenu> foodMenuList, int index, int total, int k, LinkedList<FoodMenu> tempList, List<List<FoodMenu>> result) {
int sum = tempList.stream().mapToInt(FoodMenu::getPrice).sum();
if(index==foodMenuList.size()&&sum<=total&&k==tempList.size()) {
result.add(new LinkedList<>(tempList));
}else if(index < foodMenuList.size()) {
makePolicy2(foodMenuList, index+1, total, k, tempList, result);
tempList.add(foodMenuList.get(index));
makePolicy2(foodMenuList, index+1, total, k, tempList, result);
tempList.removeLast();
}
}
/**
* 列印政策結果
*/
private static void printPolicy(List<List<FoodMenu>> list) {
int count = 1;
for(List<FoodMenu> foodMenuList : list) {
System.out.print("政策"+(count++)+":");
int totalPrice = 0;
for(FoodMenu menu : foodMenuList) {
totalPrice += menu.getPrice();
System.out.print(menu.getFoodName()+"("+menu.getPrice()+") ");
}
System.out.print(" 【總價：】"+totalPrice);
System.out.println();
}
}
}
政策一運作結果
該政策是指使用者每道菜最多隻能點一次，在總金額不超過使用者身上帶的總錢數（該demo中設定的是300元）時點所有點菜政策，政策1為0表明客戶沒有進行消費。菜名後面括号中的是菜名的單價，後面會現實沒種政策的總價。運作結果符合上述要求。
政策1: 【總價：】0
政策2:京醬肉絲(48) 【總價：】48
政策3:毛氏紅燒肉(79) 【總價：】79
政策4:毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】127
政策5:蒜末拍黃瓜(12) 【總價：】12
政策6:蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】60
政策7:蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】91
政策8:蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】139
政策9:地鍋雞(78) 【總價：】78
政策10:地鍋雞(78) 京醬肉絲(48) 【總價：】126
政策11:地鍋雞(78) 毛氏紅燒肉(79) 【總價：】157
政策12:地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】205
政策13:地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】90
政策14:地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】138
政策15:地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】169
政策16:地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】217
政策17:糖醋排骨(68) 【總價：】68
政策18:糖醋排骨(68) 京醬肉絲(48) 【總價：】116
政策19:糖醋排骨(68) 毛氏紅燒肉(79) 【總價：】147
政策20:糖醋排骨(68) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】195
政策21:糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】80
政策22:糖醋排骨(68) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】128
政策23:糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】159
政策24:糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】207
政策25:糖醋排骨(68) 地鍋雞(78) 【總價：】146
政策26:糖醋排骨(68) 地鍋雞(78) 京醬肉絲(48) 【總價：】194
政策27:糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】225
政策28:糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】273
政策29:糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】158
政策30:糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】206
政策31:糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】237
政策32:糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】285
政策33:米飯(4) 【總價：】4
政策34:米飯(4) 京醬肉絲(48) 【總價：】52
政策35:米飯(4) 毛氏紅燒肉(79) 【總價：】83
政策36:米飯(4) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】131
政策37:米飯(4) 蒜末拍黃瓜(12) 【總價：】16
政策38:米飯(4) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】64
政策39:米飯(4) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】95
政策40:米飯(4) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】143
政策41:米飯(4) 地鍋雞(78) 【總價：】82
政策42:米飯(4) 地鍋雞(78) 京醬肉絲(48) 【總價：】130
政策43:米飯(4) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】161
政策44:米飯(4) 地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】209
政策45:米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】94
政策46:米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】142
政策47:米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】173
政策48:米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】221
政策49:米飯(4) 糖醋排骨(68) 【總價：】72
政策50:米飯(4) 糖醋排骨(68) 京醬肉絲(48) 【總價：】120
政策51:米飯(4) 糖醋排骨(68) 毛氏紅燒肉(79) 【總價：】151
政策52:米飯(4) 糖醋排骨(68) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】199
政策53:米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】84
政策54:米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】132
政策55:米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】163
政策56:米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】211
政策57:米飯(4) 糖醋排骨(68) 地鍋雞(78) 【總價：】150
政策58:米飯(4) 糖醋排骨(68) 地鍋雞(78) 京醬肉絲(48) 【總價：】198
政策59:米飯(4) 糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】229
政策60:米飯(4) 糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】277
政策61:米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】162
政策62:米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】210
政策63:米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】241
政策64:米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】289
政策65:魚香肉絲(48) 【總價：】48
政策66:魚香肉絲(48) 京醬肉絲(48) 【總價：】96
政策67:魚香肉絲(48) 毛氏紅燒肉(79) 【總價：】127
政策68:魚香肉絲(48) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】175
政策69:魚香肉絲(48) 蒜末拍黃瓜(12) 【總價：】60
政策70:魚香肉絲(48) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】108
政策71:魚香肉絲(48) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】139
政策72:魚香肉絲(48) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】187
政策73:魚香肉絲(48) 地鍋雞(78) 【總價：】126
政策74:魚香肉絲(48) 地鍋雞(78) 京醬肉絲(48) 【總價：】174
政策75:魚香肉絲(48) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】205
政策76:魚香肉絲(48) 地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】253
政策77:魚香肉絲(48) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】138
政策78:魚香肉絲(48) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】186
政策79:魚香肉絲(48) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】217
政策80:魚香肉絲(48) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】265
政策81:魚香肉絲(48) 糖醋排骨(68) 【總價：】116
政策82:魚香肉絲(48) 糖醋排骨(68) 京醬肉絲(48) 【總價：】164
政策83:魚香肉絲(48) 糖醋排骨(68) 毛氏紅燒肉(79) 【總價：】195
政策84:魚香肉絲(48) 糖醋排骨(68) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】243
政策85:魚香肉絲(48) 糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】128
政策86:魚香肉絲(48) 糖醋排骨(68) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】176
政策87:魚香肉絲(48) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】207
政策88:魚香肉絲(48) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】255
政策89:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 【總價：】194
政策90:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 京醬肉絲(48) 【總價：】242
政策91:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】273
政策92:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】206
政策93:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】254
政策94:魚香肉絲(48) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】285
政策95:魚香肉絲(48) 米飯(4) 【總價：】52
政策96:魚香肉絲(48) 米飯(4) 京醬肉絲(48) 【總價：】100
政策97:魚香肉絲(48) 米飯(4) 毛氏紅燒肉(79) 【總價：】131
政策98:魚香肉絲(48) 米飯(4) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】179
政策99:魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 【總價：】64
政策100:魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】112
政策101:魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】143
政策102:魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】191
政策103:魚香肉絲(48) 米飯(4) 地鍋雞(78) 【總價：】130
政策104:魚香肉絲(48) 米飯(4) 地鍋雞(78) 京醬肉絲(48) 【總價：】178
政策105:魚香肉絲(48) 米飯(4) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】209
政策106:魚香肉絲(48) 米飯(4) 地鍋雞(78) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】257
政策107:魚香肉絲(48) 米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】142
政策108:魚香肉絲(48) 米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】190
政策109:魚香肉絲(48) 米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】221
政策110:魚香肉絲(48) 米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】269
政策111:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 【總價：】120
政策112:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 京醬肉絲(48) 【總價：】168
政策113:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 毛氏紅燒肉(79) 【總價：】199
政策114:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】247
政策115:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】132
政策116:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】180
政策117:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】211
政策118:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】259
政策119:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 【總價：】198
政策120:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 京醬肉絲(48) 【總價：】246
政策121:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 毛氏紅燒肉(79) 【總價：】277
政策122:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】210
政策123:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】258
政策124:魚香肉絲(48) 米飯(4) 糖醋排骨(68) 地鍋雞(78) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】289
政策125:螞蟻上樹(178) 【總價：】178
政策126:螞蟻上樹(178) 京醬肉絲(48) 【總價：】226
政策127:螞蟻上樹(178) 毛氏紅燒肉(79) 【總價：】257
政策128:螞蟻上樹(178) 蒜末拍黃瓜(12) 【總價：】190
政策129:螞蟻上樹(178) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】238
政策130:螞蟻上樹(178) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】269
政策131:螞蟻上樹(178) 地鍋雞(78) 【總價：】256
政策132:螞蟻上樹(178) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】268
政策133:螞蟻上樹(178) 糖醋排骨(68) 【總價：】246
政策134:螞蟻上樹(178) 糖醋排骨(68) 京醬肉絲(48) 【總價：】294
政策135:螞蟻上樹(178) 糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】258
政策136:螞蟻上樹(178) 米飯(4) 【總價：】182
政策137:螞蟻上樹(178) 米飯(4) 京醬肉絲(48) 【總價：】230
政策138:螞蟻上樹(178) 米飯(4) 毛氏紅燒肉(79) 【總價：】261
政策139:螞蟻上樹(178) 米飯(4) 蒜末拍黃瓜(12) 【總價：】194
政策140:螞蟻上樹(178) 米飯(4) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】242
政策141:螞蟻上樹(178) 米飯(4) 蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】273
政策142:螞蟻上樹(178) 米飯(4) 地鍋雞(78) 【總價：】260
政策143:螞蟻上樹(178) 米飯(4) 地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】272
政策144:螞蟻上樹(178) 米飯(4) 糖醋排骨(68) 【總價：】250
政策145:螞蟻上樹(178) 米飯(4) 糖醋排骨(68) 京醬肉絲(48) 【總價：】298
政策146:螞蟻上樹(178) 米飯(4) 糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】262
政策147:螞蟻上樹(178) 魚香肉絲(48) 【總價：】226
政策148:螞蟻上樹(178) 魚香肉絲(48) 京醬肉絲(48) 【總價：】274
政策149:螞蟻上樹(178) 魚香肉絲(48) 蒜末拍黃瓜(12) 【總價：】238
政策150:螞蟻上樹(178) 魚香肉絲(48) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】286
政策151:螞蟻上樹(178) 魚香肉絲(48) 糖醋排骨(68) 【總價：】294
政策152:螞蟻上樹(178) 魚香肉絲(48) 米飯(4) 【總價：】230
政策153:螞蟻上樹(178) 魚香肉絲(48) 米飯(4) 京醬肉絲(48) 【總價：】278
政策154:螞蟻上樹(178) 魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 【總價：】242
政策155:螞蟻上樹(178) 魚香肉絲(48) 米飯(4) 蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】290
政策156:螞蟻上樹(178) 魚香肉絲(48) 米飯(4) 糖醋排骨(68) 【總價：】298
政策二運作結果
政策二是在政策1的基礎上指定了點菜數目，該Demo中指定的菜數量是2，是以該政策集中都是數量為2的政策并且不超過使用者所帶總金額（300元）。運作結果符合上述要求。
政策1:毛氏紅燒肉(79) 京醬肉絲(48) 【總價：】127
政策2:蒜末拍黃瓜(12) 京醬肉絲(48) 【總價：】60
政策3:蒜末拍黃瓜(12) 毛氏紅燒肉(79) 【總價：】91
政策4:地鍋雞(78) 京醬肉絲(48) 【總價：】126
政策5:地鍋雞(78) 毛氏紅燒肉(79) 【總價：】157
政策6:地鍋雞(78) 蒜末拍黃瓜(12) 【總價：】90
政策7:糖醋排骨(68) 京醬肉絲(48) 【總價：】116
政策8:糖醋排骨(68) 毛氏紅燒肉(79) 【總價：】147
政策9:糖醋排骨(68) 蒜末拍黃瓜(12) 【總價：】80
政策10:糖醋排骨(68) 地鍋雞(78) 【總價：】146
政策11:米飯(4) 京醬肉絲(48) 【總價：】52
政策12:米飯(4) 毛氏紅燒肉(79) 【總價：】83
政策13:米飯(4) 蒜末拍黃瓜(12) 【總價：】16
政策14:米飯(4) 地鍋雞(78) 【總價：】82
政策15:米飯(4) 糖醋排骨(68) 【總價：】72
政策16:魚香肉絲(48) 京醬肉絲(48) 【總價：】96
政策17:魚香肉絲(48) 毛氏紅燒肉(79) 【總價：】127
政策18:魚香肉絲(48) 蒜末拍黃瓜(12) 【總價：】60
政策19:魚香肉絲(48) 地鍋雞(78) 【總價：】126
政策20:魚香肉絲(48) 糖醋排骨(68) 【總價：】116
政策21:魚香肉絲(48) 米飯(4) 【總價：】52
政策22:螞蟻上樹(178) 京醬肉絲(48) 【總價：】226
政策23:螞蟻上樹(178) 毛氏紅燒肉(79) 【總價：】257
政策24:螞蟻上樹(178) 蒜末拍黃瓜(12) 【總價：】190
政策25:螞蟻上樹(178) 地鍋雞(78) 【總價：】256
政策26:螞蟻上樹(178) 糖醋排骨(68) 【總價：】246
政策27:螞蟻上樹(178) 米飯(4) 【總價：】182
政策28:螞蟻上樹(178) 魚香肉絲(48) 【總價：】226
總結
該案例是回溯算法在現實場景中的一個簡單的應用demo，當然實際的業務中可能會有各式各樣的場景，隻要有類似的過程——求問題的解會分成若幹步，每一步又面臨同樣的選擇，此時可以考慮使用回溯算法來解決，需要注意的是回溯算法中重要的是記得要狀态回溯，想上面代碼中的
removeLast()
方法就是狀态回溯的步驟。
個人首頁：歡迎通路
以上的算法題目對應LeetCode的題号：
- 劍指 Offer II 079. 所有子集
- 劍指 Offer II 080. 含有 k 個元素的組合
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)