python:Backtracking Algorithm

项目结构# encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 22:59 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : bead.py from dataclasses import dataclass dataclass(frozenFalse) class BeadItem: 多宝手串珠子实体 bead_id: str name: str material: str color_group: str # red/green/purple/gold unit_price: float stock: int # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:00 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : jewelry.py from dataclasses import dataclass dataclass(frozenFalse) class JewelryItem: 成套首饰商品实体 sku_id: str name: str category: str # necklace / earring / bracelet / ring material: str # Au999 / 18K / S925 color: str style: str price: float stock: int has_gem: bool # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:01 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : base_rule.py from abc import ABC, abstractmethod from typing import Any, List class BaseRule(ABC): 约束规则抽象基类 abstractmethod def check(self, item: Any, path: List[Any], **kwargs) - bool: 校验单个候选物料是否满足规则 :param item: 当前待选物料 :param path: 当前已选中集合 pass # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:01 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : bracelet_rule.py from typing import Dict, List from .base_rule import BaseRule from Backtracking.dto import BeadItem class BraceletRule(BaseRule): 手串搭配约束规则 def __init__(self, max_single_color: int 4): self.max_single_color max_single_color def check(self, item: BeadItem, path: List[BeadItem], **kwargs) - bool: :param item: :param path: :param kwargs: :return: # 1. 库存校验 used_count path.count(item) if used_count item.stock: return False # 2. 色系均衡约束 color_cnt: Dict[str, int] {} for b in path: color_cnt[b.color_group] color_cnt.get(b.color_group, 0) 1 if color_cnt.get(item.color_group, 0) self.max_single_color: return False return True # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:04 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : scene_jewelry_rule.py from typing import Dict, List, Set from .base_rule import BaseRule from Backtracking.dto import JewelryItem class SceneJewelryRule(BaseRule): 场景化成套首饰约束规则 def __init__(self, scene_config: Dict): self.scene_config scene_config def check(self, item: JewelryItem, path: List[JewelryItem], **kwargs) - bool: allow_material: Set self.scene_config[allow_material] must_gem: bool self.scene_config[must_gem] # 库存 if item.stock 0: return False # 材质限制 if item.material not in allow_material: return False # 是否必须带宝石 if must_gem and not item.has_gem: return False return True staticmethod def get_scene_config(scene_type: str) - Dict: 场景配置中心新增场景只在这里扩展 :param scene_type: :return: scene_map { wedding: { allow_material: {Au999, 18K}, must_gem: True }, commute: { allow_material: {Au999, S925, 18K}, must_gem: False }, dinner: { allow_material: {18K}, must_gem: True } } return scene_map.get(scene_type, scene_map[commute]) # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:05 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : score_util.py from Backtracking.dto import BeadItem, JewelryItem def score_bracelet_scheme(scheme: list[BeadItem]) - float: 手串方案评分色系多样性优先 :param scheme: :return: color_set {b.color_group for b in scheme} diversity len(color_set) total_cost sum(b.unit_price for b in scheme) return diversity * 10 - total_cost / 200 def score_jewelry_scheme(scheme: list[JewelryItem]) - float: 成套首饰方案评分 :param scheme: :return: gem_cnt sum(1 for i in scheme if i.has_gem) stock_score sum(min(i.stock, 5) for i in scheme) return gem_cnt * 5 stock_score # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:07 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : backtrack_bracelet.py from typing import List from Backtracking.dto import BeadItem from Backtracking.rule.bracelet_rule import BraceletRule class BraceletBackTracker: def __init__(self, bead_pool: List[BeadItem], rule: BraceletRule): self.bead_pool bead_pool self.rule rule self.solutions: List[List[BeadItem]] [] def backtrack(self, path: List[BeadItem], remain: int, total_cost: float, budget: float): :param path: :param remain: :param total_cost: :param budget: :return: if remain 0: self.solutions.append(path.copy()) return if total_cost budget: return for bead in self.bead_pool: if not self.rule.check(bead, path): continue path.append(bead) self.backtrack(path, remain - 1, total_cost bead.unit_price, budget) path.pop() def run(self, target_count: int, budget: float) - List[List[BeadItem]]: :param target_count: :param budget: :return: self.solutions.clear() self.backtrack([], target_count, 0.0, budget) return self.solutions # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:08 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : backtrack_jewelry.py from typing import List, Set from Backtracking.dto import JewelryItem from Backtracking.rule.scene_jewelry_rule import SceneJewelryRule class JewelrySceneBackTracker: def __init__(self, goods_pool: List[JewelryItem], rule: SceneJewelryRule): self.goods_pool goods_pool self.rule rule self.solutions: List[List[JewelryItem]] [] def backtrack( self, start_idx: int, selected: List[JewelryItem], total_price: float, budget: float, target_categories: Set[str] ): :param start_idx: :param selected: :param total_price: :param budget: :param target_categories: :return: selected_cats {x.category for x in selected} if selected_cats target_categories: self.solutions.append(selected.copy()) return if total_price budget: return for i in range(start_idx, len(self.goods_pool)): item self.goods_pool[i] if item.category in selected_cats: continue if not self.rule.check(item, selected): continue selected.append(item) self.backtrack(i 1, selected, total_price item.price, budget, target_categories) selected.pop() def run(self, budget: float, target_categories: Set[str]) - List[List[JewelryItem]]: :param budget: :param target_categories: :return: self.solutions.clear() self.backtrack(0, [], 0.0, budget, target_categories) return self.solutions # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:09 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : bracelet_service.py from typing import List from Backtracking.dto import BeadItem from Backtracking.core import BraceletBackTracker from Backtracking.rule.bracelet_rule import BraceletRule from Backtracking.common import score_bracelet_scheme class BraceletMatchService: 手串搭配业务服务层封装算法调用、排序、截断 def __init__(self, bead_pool: List[BeadItem]): self.bead_pool bead_pool def match( self, target_count: int, budget: float, max_color_limit: int 4, top_n: int 6 ) - List[List[BeadItem]]: :param target_count: :param budget: :param max_color_limit: :param top_n: :return: rule BraceletRule(max_single_colormax_color_limit) tracker BraceletBackTracker(self.bead_pool, rule) schemes tracker.run(target_count, budget) # 业务后处理打分排序只返回TopN schemes.sort(keyscore_bracelet_scheme, reverseTrue) return schemes[:top_n] # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:10 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : jewelry_scene_service.py from typing import List, Set from Backtracking.dto import JewelryItem from Backtracking.core import JewelrySceneBackTracker from Backtracking.rule.scene_jewelry_rule import SceneJewelryRule from Backtracking.common import score_jewelry_scheme class JewelrySceneMatchService: 场景成套首饰业务服务 def __init__(self, goods_pool: List[JewelryItem]): self.goods_pool goods_pool def match_by_scene( self, scene: str, budget: float, target_categories: Set[str], top_n: int 8 ) - List[List[JewelryItem]]: :param scene: :param budget: :param target_categories: :param top_n: :return: scene_conf SceneJewelryRule.get_scene_config(scene) rule SceneJewelryRule(scene_conf) tracker JewelrySceneBackTracker(self.goods_pool, rule) schemes tracker.run(budget, target_categories) schemes.sort(keyscore_jewelry_scheme, reverseTrue) return schemes[:top_n]调用# encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Backtracking Algorithm # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/22 23:12 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : BacktrackingBll.py from Backtracking.dto import BeadItem, JewelryItem from Backtracking.service import BraceletMatchService, JewelrySceneMatchService class BacktrackingBll(object): def test_bracelet_match(self): :return: bead_pool [ BeadItem(B01, 南红圆珠, 南红, red, 168, 4), BeadItem(B02, 和田玉圆珠, 和田玉, green, 198, 5), BeadItem(B03, 紫水晶, 紫水晶, purple, 128, 4), BeadItem(B04, 足金隔珠, 足金, gold, 320, 3), ] svc BraceletMatchService(bead_pool) result svc.match(target_count8, budget2000) print( 多宝手串搭配方案 ) for idx, scheme in enumerate(result, 1): total sum(b.unit_price for b in scheme) names [b.name for b in scheme] print(f方案{idx} 总价:{total:.2f} 珠子:{names}) def test_jewelry_scene_match(self): :return: goods_pool [ JewelryItem(N001, 碎钻项链, necklace, 18K, white, luxury, 3299, 12, True), JewelryItem(N003, 素金项链, necklace, Au999, yellow, minimalist, 2199, 9, False), JewelryItem(E001, 白钻耳饰, earring, 18K, white, luxury, 2199, 15, True), JewelryItem(E003, 素金耳饰, earring, Au999, yellow, minimalist, 1399, 11, False), ] svc JewelrySceneMatchService(goods_pool) target_cats {necklace, earring} print(\n 婚嫁场景 ) wedding svc.match_by_scene(wedding, budget8000, target_categoriestarget_cats) for item_set in wedding: print([x.name for x in item_set], 总价, sum(x.price for x in item_set)) print(\n 通勤场景 ) commute svc.match_by_scene(commute, budget5000, target_categoriestarget_cats) for item_set in commute: print([x.name for x in item_set], 总价, sum(x.price for x in item_set)) def Demo(self): :return: self.test_bracelet_match() self.test_jewelry_scene_match()输出