Notes
  • Introduce
  • Go
    • Grammar
      • Basic
      • Goroutines & Channels
      • Test
    • System Library
      • Module
      • sync
      • context
      • net
    • Concurrency in Go
    • The Go Memory Model
    • Code Snippet
  • Rust
    • The Rust Programming Language
    • Rust by Example
  • JAVA
    • Preface
    • Grammar
      • Basic
      • Data Types
      • Operator
      • Exceptions
    • Class Libraries
      • Collection
      • Stream
      • IO
      • NIO
      • RMI
    • Concurrency
      • Preface
      • JMM
      • Synchronized & CAS
      • Deadlock
      • Thread
      • Lock & Condition
      • Utility Class
      • Thread-safe Collection
      • Atomic Class
      • Fork/Join
      • Concurrency Design Patterns
        • Immutable
        • Copy-on-Write
        • ThreadLocal
        • Multitheading If
        • Division
    • JVM
      • Class & Instance Initialization
      • Runtime Data Area
      • Garbage Collection
    • Web Container
      • Tomcat Architecture
      • Jetty Architecture
    • Spring
    • Tuning
      • Programming
  • Computer Science
    • Computer Organization
    • Algorithm
      • Complexity
      • Linear List
      • Sort
      • Binary Search
      • Skip List
      • Hash Table
      • Tree
      • Graph
      • String Matching
      • Bloom Filter
      • Greedy Algorithm
      • Divide and Conquer
      • Back Tracking
      • Dynamic Programming
    • Network Protocol
      • Pysical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer
      • Application layer
      • HTTP
      • HTTP/2 in Action
    • Operating System
      • Basic
      • System Initialization
      • Diagnostic Tools
      • CPU Diagnosis
      • Memory Diagnosis
      • Disk Diagnosis
      • Network Diagnosis
      • Monitor System
    • Design Patterns
      • UML
      • OOP
      • Principle
      • Refactoring & Specification
      • Creational
        • Singleton
        • Factory
        • Builder
        • Prototype
      • Structural
        • Proxy
        • Bridge
        • Decorator
        • Adapter
        • Facade
        • Composite
        • FlyWeight
      • Behavioral
        • Observer
        • Template Method
        • Strategy
        • State
        • Iterator
        • Chain of Responsibility
    • Distributed System
      • Protocol & Algorithm
      • Transcation
      • Theory
      • Resource Management
      • Scheduling
      • Computing
      • Message Queue
      • Cache
      • Consistent Hashing
  • database
    • InfluxDB
      • In-Memory Index
      • Meta
    • MySQL
      • SQL
      • Architecture
      • Log
      • Transaction
      • Indexing
      • Lock
      • Storage
    • Redis
    • Elasticsearch
      • Local Debug
    • HBase
    • Kafka
    • ZooKeeper
  • Reading
    • RocketMQ
    • 演说之禅
    • So Good They Can't Ignore You
    • 学会提问
    • Lecture
  • Other
    • v2ray
    • Kubernetes
    • Git
    • Maven
    • Anaconda And Conda
    • Fuck! Shit!
      • Remove Final by Reflection
      • Ingress Host
      • ExecuterService submit
  • Open source contribution
Powered by GitBook
On this page
  • 案例
  • 0-1 背包
  • 正则

Was this helpful?

  1. Computer Science
  2. Algorithm

Back Tracking

PreviousDivide and ConquerNextDynamic Programming

Last updated 5 years ago

Was this helpful?

回溯的处理思想,类似于枚举。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有的解,避免重复和遗漏,把问题求解的过程分为多个阶段。每个阶段,会有多个选择,随意选择一个,若发现这个选择不满足条件,则回到上一步,做另外一个选择。

比如深度优先遍历即使用的回溯思想。

回溯算法一般适用用递归来实现。剪枝操作是提高回溯效率的一种技巧。

案例

0-1 背包

问题:一个背包总承重 W kg,有 n 个重量不等的物体,选择几件物品装到背包中,使背包中的总重量最大。

注意:此问题与区别在于这里的物体不能分割,只能选择装或不装,所以叫做 0-1 问题。此类问题用效率更高。

思路:用回溯思想的话,若有 n 个物体,把问题分为 n 个阶段,每个阶段对应是否选择物品。可以用一点剪枝技巧,当已经选择的物品超过 W 后,就停止后面的阶段。

private int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
private int[] weight = {2,2,4,6,3}; // 每个物品的重量
private int n = 5; // 物品个数
private int w = 9; // 背包重量
// cw表示当前已经装进去的物品的重量和;i表示考察到哪个物品了;
// 调用方式:f(0, 0)
public void f(int i, int cw) {
  if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw); // 不选择此阶段的物品
  if (cw + weight[i] <= w) {// 已经超过可以背包承受的重量的时候,就不要再装了
    f(i+1,cw + weight[i]); // 选择此阶段的物品
  }
}

正则

LeetCode 20:生成有效括号组合。
LeetCode 51:N 皇后问题,输出所有解。
LeetCode 52:N 皇后问题,输出解的个数。
LeetCode 37:数独的解。
LeetCode 79:二维字符数组中是否存在某个字符串。
LeetCode 212:二维字符数组中找出存在的字符串。
动态规划
贪心算法中的背包问题