java: Backtracking Algorithm

项目结构/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:25 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : BraceletBackTracker.java * explain : 学习 类 **/ package Backtracking.core; import Backtracking.dto.BeadItem; import Backtracking.rule.IBaseRule; import java.util.ArrayList; import java.util.List; public class BraceletBackTracker { private final ListBeadItem beadPool; private final IBaseRuleBeadItem rule; private final ListListBeadItem solutions new ArrayList(); public BraceletBackTracker(ListBeadItem beadPool, IBaseRuleBeadItem rule) { this.beadPool beadPool; this.rule rule; } private void backtrack(ListBeadItem path, int remain, double totalCost, double budget) { if (remain 0) { solutions.add(new ArrayList(path)); return; } if (totalCost budget) { return; } for (BeadItem bead : beadPool) { if (!rule.check(bead, path)) { continue; } path.add(bead); backtrack(path, remain - 1, totalCost bead.getUnitPrice(), budget); path.remove(path.size() - 1); } } public ListListBeadItem run(int targetCount, double budget) { solutions.clear(); backtrack(new ArrayList(), targetCount, 0.0, budget); return solutions; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:26 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : JewelrySceneBackTracker.java * explain : 学习 类 **/ package Backtracking.core; import Backtracking.dto.JewelryItem; import Backtracking.rule.IBaseRule; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class JewelrySceneBackTracker { private final ListJewelryItem goodsPool; private final IBaseRuleJewelryItem rule; private final ListListJewelryItem solutions new ArrayList(); public JewelrySceneBackTracker(ListJewelryItem goodsPool, IBaseRuleJewelryItem rule) { this.goodsPool goodsPool; this.rule rule; } private void backtrack(int startIdx, ListJewelryItem selected, double totalPrice, double budget, SetString targetCategories) { SetString selectedCats new HashSet(); for (JewelryItem item : selected) { selectedCats.add(item.getCategory()); } boolean complete true; for (String cat : targetCategories) { if (!selectedCats.contains(cat)) { complete false; break; } } if (complete) { solutions.add(new ArrayList(selected)); return; } if (totalPrice budget) { return; } for (int i startIdx; i goodsPool.size(); i) { JewelryItem item goodsPool.get(i); if (selectedCats.contains(item.getCategory())) { continue; } if (!rule.check(item, selected)) { continue; } selected.add(item); backtrack(i 1, selected, totalPrice item.getPrice(), budget, targetCategories); selected.remove(selected.size() - 1); } } public ListListJewelryItem run(double budget, SetString targetCategories) { solutions.clear(); backtrack(0, new ArrayList(), 0.0, budget, targetCategories); return solutions; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:21 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : BeadItem.java * explain : 学习 类 **/ package Backtracking.dto; /** * 多宝手串珠子实体 */ public class BeadItem { private String beadId; private String name; private String material; private String colorGroup; // red/green/purple/gold private double unitPrice; private int stock; public String getBeadId() { return beadId; } public void setBeadId(String beadId) { this.beadId beadId; } public String getName() { return name; } public void setName(String name) { this.name name; } public String getMaterial() { return material; } public void setMaterial(String material) { this.material material; } public String getColorGroup() { return colorGroup; } public void setColorGroup(String colorGroup) { this.colorGroup colorGroup; } public double getUnitPrice() { return unitPrice; } public void setUnitPrice(double unitPrice) { this.unitPrice unitPrice; } public int getStock() { return stock; } public void setStock(int stock) { this.stock stock; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:21 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : JewelryItem.java * explain : 学习 类 **/ package Backtracking.dto; /** * 成套首饰商品 */ public class JewelryItem { private String skuId; private String name; private String category; // necklace / earring private String material; private String color; private String style; private double price; private int stock; private boolean hasGem; public String getSkuId() { return skuId; } public void setSkuId(String skuId) { this.skuId skuId; } public String getName() { return name; } public void setName(String name) { this.name name; } public String getCategory() { return category; } public void setCategory(String category) { this.category category; } public String getMaterial() { return material; } public void setMaterial(String material) { this.material material; } public String getColor() { return color; } public void setColor(String color) { this.color color; } public String getStyle() { return style; } public void setStyle(String style) { this.style style; } public double getPrice() { return price; } public void setPrice(double price) { this.price price; } public int getStock() { return stock; } public void setStock(int stock) { this.stock stock; } public boolean isHasGem() { return hasGem; } public void setHasGem(boolean hasGem) { this.hasGem hasGem; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:22 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : BraceletRule.java * explain : 学习 类 **/ package Backtracking.rule; import Backtracking.dto.BeadItem; import java.util.HashMap; import java.util.List; import java.util.Map; public class BraceletRule implements IBaseRuleBeadItem { private final int maxSingleColor; public BraceletRule(int maxSingleColor) { this.maxSingleColor maxSingleColor; } Override public boolean check(BeadItem item, ListBeadItem path) { // 库存校验同珠子选用次数不能超过库存 int used 0; for (BeadItem b : path) { if (b.getBeadId().equals(item.getBeadId())) { used; } } if (used item.getStock()) { return false; } // 色系均衡约束 MapString, Integer colorCnt new HashMap(); for (BeadItem b : path) { colorCnt.put(b.getColorGroup(), colorCnt.getOrDefault(b.getColorGroup(), 0) 1); } int current colorCnt.getOrDefault(item.getColorGroup(), 0); if (current maxSingleColor) { return false; } return true; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:22 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : IBaseRule.java * explain : 学习 类 **/ package Backtracking.rule; import java.util.List; /** * 约束规则顶层接口 * param T BeadItem / JewelryItem */ public interface IBaseRuleT { boolean check(T item, ListT path); } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:24 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : SceneConfig.java * explain : 学习 类 **/ package Backtracking.rule; import java.util.*; public class SceneConfig { private SetString allowMaterial; private boolean mustGem; public SetString getAllowMaterial() { return allowMaterial; } public void setAllowMaterial(SetString allowMaterial) { this.allowMaterial allowMaterial; } public boolean isMustGem() { return mustGem; } public void setMustGem(boolean mustGem) { this.mustGem mustGem; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:23 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : SceneJewelryRule.java * explain : 学习 类 **/ package Backtracking.rule; import Backtracking.dto.JewelryItem; import java.util.*; public class SceneJewelryRule implements IBaseRuleJewelryItem { private final SceneConfig config; public SceneJewelryRule(SceneConfig config) { this.config config; } Override public boolean check(JewelryItem item, ListJewelryItem path) { if (item.getStock() 0) { return false; } if (!config.getAllowMaterial().contains(item.getMaterial())) { return false; } if (config.isMustGem() !item.isHasGem()) { return false; } return true; } /** * 场景配置中心新增场景仅在此扩展 */ public static SceneConfig getSceneConfig(String sceneType) { MapString, SceneConfig sceneMap new HashMap(); SceneConfig wedding new SceneConfig(); wedding.setAllowMaterial(new HashSet(List.of(Au999, 18K))); wedding.setMustGem(true); sceneMap.put(wedding, wedding); SceneConfig commute new SceneConfig(); commute.setAllowMaterial(new HashSet(List.of(Au999, S925, 18K))); commute.setMustGem(false); sceneMap.put(commute, commute); SceneConfig dinner new SceneConfig(); dinner.setAllowMaterial(new HashSet(List.of(18K))); dinner.setMustGem(true); sceneMap.put(dinner, dinner); return sceneMap.getOrDefault(sceneType, commute); } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:25 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : ScoreUtil.java * explain : 学习 类 **/ package Backtracking.common; import Backtracking.dto.BeadItem; import Backtracking.dto.JewelryItem; import java.util.HashSet; import java.util.List; import java.util.Set; public class ScoreUtil { /** * 手串方案评分色系多样性优先 */ public static double scoreBraceletScheme(ListBeadItem scheme) { SetString colorSet new HashSet(); double totalCost 0.0; for (BeadItem b : scheme) { colorSet.add(b.getColorGroup()); totalCost b.getUnitPrice(); } double diversity colorSet.size(); return diversity * 10 - totalCost / 200; } /** * 成套首饰方案评分 */ public static double scoreJewelryScheme(ListJewelryItem scheme) { int gemCnt 0; int stockScore 0; for (JewelryItem item : scheme) { if (item.isHasGem()) { gemCnt; } stockScore Math.min(item.getStock(), 5); } return gemCnt * 5 stockScore; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:27 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : BraceletMatchService.java * explain : 学习 类 **/ package Backtracking.service; import Backtracking.common.ScoreUtil; import Backtracking.core.BraceletBackTracker; import Backtracking.dto.BeadItem; import Backtracking.rule.BraceletRule; import Backtracking.rule.IBaseRule; import java.util.ArrayList; import java.util.Comparator; import java.util.List; public class BraceletMatchService { private final ListBeadItem beadPool; public BraceletMatchService(ListBeadItem beadPool) { this.beadPool beadPool; } public ListListBeadItem match(int targetCount, double budget, int maxColorLimit, int topN) { IBaseRuleBeadItem rule new BraceletRule(maxColorLimit); BraceletBackTracker tracker new BraceletBackTracker(beadPool, rule); ListListBeadItem schemes tracker.run(targetCount, budget); // 按评分降序 schemes.sort((a, b) - Double.compare(ScoreUtil.scoreBraceletScheme(b), ScoreUtil.scoreBraceletScheme(a))); if (schemes.size() topN) { schemes schemes.subList(0, topN); } return new ArrayList(schemes); } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:28 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : JewelrySceneMatchService.java * explain : 学习 类 **/ package Backtracking.service; import Backtracking.common.ScoreUtil; import Backtracking.core.JewelrySceneBackTracker; import Backtracking.dto.JewelryItem; import Backtracking.rule.IBaseRule; import Backtracking.rule.SceneJewelryRule; import Backtracking.rule.SceneConfig; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Set; public class JewelrySceneMatchService { private final ListJewelryItem goodsPool; public JewelrySceneMatchService(ListJewelryItem goodsPool) { this.goodsPool goodsPool; } public ListListJewelryItem matchByScene(String scene, double budget, SetString targetCategories, int topN) { SceneConfig cfg SceneJewelryRule.getSceneConfig(scene); IBaseRuleJewelryItem rule new SceneJewelryRule(cfg); JewelrySceneBackTracker tracker new JewelrySceneBackTracker(goodsPool, rule); ListListJewelryItem schemes tracker.run(budget, targetCategories); schemes.sort((a, b) - Double.compare(ScoreUtil.scoreJewelryScheme(b), ScoreUtil.scoreJewelryScheme(a))); if (schemes.size() topN) { schemes schemes.subList(0, topN); } return new ArrayList(schemes); } }调用/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述Backtracking Algorithm * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/23 - 22:29 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : BacktrackingBll.java * explain : 学习 类 **/ package Bll; import Backtracking.dto.BeadItem; import Backtracking.dto.JewelryItem; import Backtracking.service.BraceletMatchService; import Backtracking.service.JewelrySceneMatchService; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.stream.Collectors; public class BacktrackingBll { static void testBraceletMatch() { ListBeadItem beadPool new ArrayList(); BeadItem b1 new BeadItem(); b1.setBeadId(B01); b1.setName(南红圆珠); b1.setMaterial(南红); b1.setColorGroup(red); b1.setUnitPrice(168); b1.setStock(4); BeadItem b2 new BeadItem(); b2.setBeadId(B02); b2.setName(和田玉圆珠); b2.setMaterial(和田玉); b2.setColorGroup(green); b2.setUnitPrice(198); b2.setStock(5); BeadItem b3 new BeadItem(); b3.setBeadId(B03); b3.setName(紫水晶); b3.setMaterial(紫水晶); b3.setColorGroup(purple); b3.setUnitPrice(128); b3.setStock(4); BeadItem b4 new BeadItem(); b4.setBeadId(B04); b4.setName(足金隔珠); b4.setMaterial(足金); b4.setColorGroup(gold); b4.setUnitPrice(320); b4.setStock(3); beadPool.add(b1); beadPool.add(b2); beadPool.add(b3); beadPool.add(b4); BraceletMatchService svc new BraceletMatchService(beadPool); ListListBeadItem result svc.match(8, 2000, 4, 6); System.out.println( 多宝手串搭配方案 ); for (int idx 0; idx result.size(); idx) { ListBeadItem scheme result.get(idx); double total scheme.stream().mapToDouble(BeadItem::getUnitPrice).sum(); String names scheme.stream().map(BeadItem::getName).collect(Collectors.joining(, )); System.out.printf(方案%d 总价:%.2f 珠子:[%s]%n, idx 1, total, names); } } static void testJewelrySceneMatch() { ListJewelryItem goodsPool new ArrayList(); JewelryItem j1 new JewelryItem(); j1.setSkuId(N001); j1.setName(碎钻项链); j1.setCategory(necklace); j1.setMaterial(18K); j1.setColor(white); j1.setStyle(luxury); j1.setPrice(3299); j1.setStock(12); j1.setHasGem(true); JewelryItem j2 new JewelryItem(); j2.setSkuId(N003); j2.setName(素金项链); j2.setCategory(necklace); j2.setMaterial(Au999); j2.setColor(yellow); j2.setStyle(minimalist); j2.setPrice(2199); j2.setStock(9); j2.setHasGem(false); JewelryItem j3 new JewelryItem(); j3.setSkuId(E001); j3.setName(白钻耳饰); j3.setCategory(earring); j3.setMaterial(18K); j3.setColor(white); j3.setStyle(luxury); j3.setPrice(2199); j3.setStock(15); j3.setHasGem(true); JewelryItem j4 new JewelryItem(); j4.setSkuId(E003); j4.setName(素金耳饰); j4.setCategory(earring); j4.setMaterial(Au999); j4.setColor(yellow); j4.setStyle(minimalist); j4.setPrice(1399); j4.setStock(11); j4.setHasGem(false); goodsPool.add(j1); goodsPool.add(j2); goodsPool.add(j3); goodsPool.add(j4); JewelrySceneMatchService svc new JewelrySceneMatchService(goodsPool); SetString targetCats new HashSet(); targetCats.add(necklace); targetCats.add(earring); System.out.println(\n 婚嫁场景 ); ListListJewelryItem wedding svc.matchByScene(wedding, 8000, targetCats, 8); for (ListJewelryItem set : wedding) { String names set.stream().map(JewelryItem::getName).collect(Collectors.joining(, )); double total set.stream().mapToDouble(JewelryItem::getPrice).sum(); System.out.printf([%s] 总价 %.2f%n, names, total); } System.out.println(\n 通勤场景 ); ListListJewelryItem commute svc.matchByScene(commute, 5000, targetCats, 8); for (ListJewelryItem set : commute) { String names set.stream().map(JewelryItem::getName).collect(Collectors.joining(, )); double total set.stream().mapToDouble(JewelryItem::getPrice).sum(); System.out.printf([%s] 总价 %.2f%n, names, total); } } public void Demo() { testBraceletMatch(); testJewelrySceneMatch(); } }输出