01背包回溯法复杂度_回溯算法详细总结

作者：煮酒与君饮 | 2024-08-22 00:47:51

踩

01背包问题回溯法时间复杂度

@[TOC]

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回到上一步，重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

解空间结构：

最简单的装载问题描述：给定n个货物、每个货物重量为Wi，一艘船的载货总重量为W。问如何选择货物装载使得船尽可能多的装载货物而不翻船？输入：货物数量n，每个货物的重量输出：选择的货物i、最大的货物装载量

分析这个问题其实很像0-1背包问题，只不过约束条件少了价值。货物装与不装使用Xi={0,1}表示，0表示不装，1表示装。则

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/1013982