序列覆蓋算法

Question

我正在尋找一種算法來解決以下問題：

鑑於從0序列n包含數字到9和m其他序列，找出最小的（含最低金額）系列的序列等於n。

例

n = 123456 
m1 = 12 
m2 = 34 
m3 = 56 
m4 = 3456 
output = m1 + m4 = 123456 

事情我已經想到了到目前爲止

基本貪婪技術採用FSM或者特里樹樹查找最長序列中開始安裝：

while n not null 
    longest = the longest sequence fitting in the beginning of n 
    print longest 
    n = n - longest 

反例

n = 123456 
m1 = 12 
m2 = 1 
m3 = 23456 
m4 = 3 
m5 = 4 
m6 = 5 
m7 = 6 
algorithm will find m1 + m4 + m5 + m6 + m7 (12 + 3 + 4 + 5 + 6) 
algorithm should find m2 + m3 (1 + 23456) 

另一個貪心法

array = {n} #this represents words to be matched 
while array not empty 
    (word, index) = find longest sequence covering part of any word in array and its index 
    split array[index] into two words - first before found word, second after it 
    if any of those split items is null 
     remove it 

反例

n = 12345678 
m1 = 3456 
m2 = 1 
m3 = 2 
m4 = 7 
m5 = 8 
m6 = 123 
m7 = 45 
m8 = 678 
algorithm will find m2 + m3 + m1 + m4 + m5 (1 + 2 + 3456 + 7 + 8) 
algorithm should find m6 + m7 + m8 (123 + 45 + 678) 

Answer 1

可以使用動態編程來計算由步驟的結果的步驟。

允許定義序列s（i），其生成第i個字符n的最短序列。

隨着最後一個例子的數據，第（I）的值是：

s(0) = { }  
s(1) = { m2 } 
s(2) = { m2 + m3 } 
s(3) = { m6 } 
s(4) = { }  (no sequence can generate "1234") 
s(5) = { m6 + m7 } 
s(6) = { m2 + m3 + m1 } 
s(7) = { m2 + m3 + m1 + m4 } 
s(8) = { m6 + m7 + m8 } 

你必須計算s(1)到s(n)秩序。在每一步i你看看所有的序列從開始到s(0)和s(i-1)保持最短。

例如，對於s(8)，你會發現你有兩個解決方案：

s(8) = s(5) + m8 
s(8) = s(7) + m5 

而且你保持最短。

算法：

function computeBestSequence(word, list of subsequences m) 

let s(0) := {} 
for i from 1 to n  // We will compute s(i) 
    let minSize := +inf. 
    for j from 0 to i - 1   
     for all sequences mx from m1 to m9 
     if s(j) + mx = the first i char of word 
      if size of s(j) + mx is less than minSize 
       minSize := size of s(j) + mx 
       s(i) := s(j) + mx 

---

編輯：

該算法可以簡化爲只使用兩個循環：

let s(0) := {} 
for i from 1 to n  // We will compute s(i) 
    let minSize := +inf. 
    for all sequences mx from m1 to m9 
     let j := i - mx.length 
     if s(j) + mx = the first i char of word 
      if size of s(j) + mx is less than minSize 
       minSize := size of s(j) + mx 
       s(i) := s(j) + mx 

Answer 2

基於obourgains回答他的編輯Java代碼版本：

import java.util.LinkedList; 
import java.util.List; 

public class BestSequence { 

public static List<String> match(String word, List<String> subsequences) { 
    int n = word.length(); 

    //let s(0) := {} 
    List<List<String>> s = new LinkedList<>(); 
    for(int i = 0; i <= n; i++) 
     s.add(new LinkedList<>()); 

    //for i from 1 to n 
    for(int i = 1; i <= n; i++) { 
     //let minSize := +inf. 
     int minSize = Integer.MAX_VALUE; 

     //for all sequences mx from m1 to m9 
     for(String mx : subsequences) { 
      //let j := i - mx.length 
      int j = i - mx.length(); 

      if(j < 0) 
       continue; 

      //if s(j) + mx = the first i char of word 
      if(word.substring(0, i).equals(concat(s.get(j)) + mx)) { 
       //if size of s(j) + mx is less than minSize 
       if(s.get(j).size() + 1 < minSize) { 
        //minSize := size of s(j) + mx 
        minSize = s.get(j).size() + 1; 
        //s(i) := s(j) + mx 
        List<String> sj = new LinkedList<>(s.get(j)); 
        sj.add(mx); 
        s.set(i, sj); 
       } 
      } 
     } 
    } 
    return s.get(n); 
} 

private static String concat(List<String> strs) { 
    String s = ""; 
    for(String str : strs) { 
     s += str; 
    } 
    return s; 
} 

} 

測試：

@Test 
public void bestSequenceTest() { 
    List<String> l = BestSequence.match("123456", Arrays.asList("12", "34", "56", "3456")); 
    System.out.println(l); 
} 

輸出：

[12, 3456]