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 List<BeadItem> beadPool;
private final IBaseRule<BeadItem> rule;
private final List<List<BeadItem>> solutions = new ArrayList<>();

public BraceletBackTracker(List<BeadItem> beadPool, IBaseRule<BeadItem> rule) {
this.beadPool = beadPool;
this.rule = rule;
}

private void backtrack(List<BeadItem> 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 List<List<BeadItem>> 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 List<JewelryItem> goodsPool;
private final IBaseRule<JewelryItem> rule;
private final List<List<JewelryItem>> solutions = new ArrayList<>();

public JewelrySceneBackTracker(List<JewelryItem> goodsPool, IBaseRule<JewelryItem> rule) {
this.goodsPool = goodsPool;
this.rule = rule;
}

private void backtrack(int startIdx, List<JewelryItem> selected, double totalPrice, double budget, Set<String> targetCategories) {
Set<String> 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 List<List<JewelryItem>> run(double budget, Set<String> 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 IBaseRule<BeadItem> {

private final int maxSingleColor;

public BraceletRule(int maxSingleColor) {
this.maxSingleColor = maxSingleColor;
}

@Override
public boolean check(BeadItem item, List<BeadItem> path) {
// 库存校验：同珠子选用次数不能超过库存
int used = 0;
for (BeadItem b : path) {
if (b.getBeadId().equals(item.getBeadId())) {
used++;
}
}
if (used >= item.getStock()) {
return false;
}

// 色系均衡约束
Map<String, 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 IBaseRule<T> {
boolean check(T item, List<T> 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 Set<String> allowMaterial;
private boolean mustGem;

public Set<String> getAllowMaterial() {
return allowMaterial;
}

public void setAllowMaterial(Set<String> 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 IBaseRule<JewelryItem> {

private final SceneConfig config;

public SceneJewelryRule(SceneConfig config) {
this.config = config;
}

@Override
public boolean check(JewelryItem item, List<JewelryItem> 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) {
Map<String, 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(List<BeadItem> scheme) {
Set<String> 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(List<JewelryItem> 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 List<BeadItem> beadPool;

public BraceletMatchService(List<BeadItem> beadPool) {
this.beadPool = beadPool;
}

public List<List<BeadItem>> match(int targetCount, double budget, int maxColorLimit, int topN) {
IBaseRule<BeadItem> rule = new BraceletRule(maxColorLimit);
BraceletBackTracker tracker = new BraceletBackTracker(beadPool, rule);
List<List<BeadItem>> 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 List<JewelryItem> goodsPool;

public JewelrySceneMatchService(List<JewelryItem> goodsPool) {
this.goodsPool = goodsPool;
}

public List<List<JewelryItem>> matchByScene(String scene, double budget, Set<String> targetCategories, int topN) {
SceneConfig cfg = SceneJewelryRule.getSceneConfig(scene);
IBaseRule<JewelryItem> rule = new SceneJewelryRule(cfg);
JewelrySceneBackTracker tracker = new JewelrySceneBackTracker(goodsPool, rule);
List<List<JewelryItem>> 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() {
List<BeadItem> 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);
List<List<BeadItem>> result = svc.match(8, 2000, 4, 6);

System.out.println("===== 多宝手串搭配方案 =====");
for (int idx = 0; idx < result.size(); idx++) {
List<BeadItem> 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() {
List<JewelryItem> 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);
Set<String> targetCats = new HashSet<>();
targetCats.add("necklace");
targetCats.add("earring");

System.out.println("\\n===== 婚嫁场景 =====");
List<List<JewelryItem>> wedding = svc.matchByScene("wedding", 8000, targetCats, 8);
for (List<JewelryItem> 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===== 通勤场景 =====");
List<List<JewelryItem>> commute = svc.matchByScene("commute", 5000, targetCats, 8);
for (List<JewelryItem> 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();
}
}

输出：