被xx跳動(dòng)大佬使勁兒蹂躪了一把，趕緊回來總結(jié)總結(jié)
別看到是背包問題就跑掉了昂, 這篇博客是頭條大佬丟給我的最后一個(gè)問題，給你們踩坑了

首先看這樣一個(gè)界面

1. 創(chuàng)造價(jià)值概念

背包問題中有這樣的概念：按照性價(jià)比排序。文本本身沒有價(jià)值這一說，更不用說性價(jià)比了。所以我們可以吧文本看成平級(jí)的，即性價(jià)比相等。所以，當(dāng)標(biāo)簽長(zhǎng)度為3的時(shí)候，我們將它的價(jià)值默認(rèn)為3，以此類推，得到所返回標(biāo)簽的價(jià)值。此時(shí)的性價(jià)比都為1，所以這里不用針對(duì)性價(jià)比排序。

2. 背包算法的思想

經(jīng)過轉(zhuǎn)換之后，我們的問題就完全符合0-1背包的模型了。
我們假設(shè)，獲得的字符串為

1. H
2. SX
3. GCX
4. YYWX

背包算法是動(dòng)態(tài)規(guī)劃的一種，所有的問題都能通過分為小問題的形式來解決。我們這里分的小問題，就是放不放第N個(gè)。如果能放，計(jì)算當(dāng)前的最大價(jià)值，如果不放，沿用上一個(gè)規(guī)模的價(jià)值。既然是動(dòng)態(tài)規(guī)劃 , 那我們免不了要畫一個(gè)二維數(shù)組或者表格來輔助理解問題了 .

以i 為縱軸,代表物品編號(hào) , j 為橫軸 , 代表當(dāng)背包容量為j時(shí) , dp 代表當(dāng)前最大價(jià)值
為什么畫表呢 ?這是為了縮減問題規(guī)模 . 比如物品為1 背包容量為1 是的最優(yōu)解很定很好處理 , 那么我們以此為依據(jù) , 開始擴(kuò)充問題規(guī)模, 物品為12 , 背包容量為2 為3 為4是的情況 .

我們可以得出狀態(tài)轉(zhuǎn)換方程：

1. dp [ i, j ]=0 , i | j=0 (背包0容量時(shí)價(jià)值為0; 不放任何物品時(shí),價(jià)值為0)
2. dp [ i, j ]=MAX( dp[ i-1, j ] , dp [ i-1, j- w[i] ]+v[i]) (背包容量不為0時(shí) , 看強(qiáng)行放入物品時(shí)的價(jià)值與不放入物品的價(jià)值 , 這里的強(qiáng)行放入指的是移除已放入物品 , 直到可放入為止 . 看上去是不是不好理解 ?其實(shí)我們?cè)谇懊婵s減問題規(guī)模的時(shí)候已經(jīng)解出來了)
   這里舉幾個(gè)例子輔助理解一下

• 根據(jù)步驟1 我們先能畫出如圖的表格(原諒我屎一般的excel):

  
  

接下來要填寫dp(1,1)單元格的數(shù)據(jù)了 , 根據(jù)上面的公式帶入i=1,j=1
得到公式:
dp(1,1)=MAX(dp (0,1 ) , dp(0 , i- 1) +1) = 1 依次填滿第二行

再舉個(gè)例子: dp[3,5]
dp[3,5]=MAX(dp[ 2,5 ] , dp[ 2,5-3] +3 ) =MAX(3, 2+3) =5
按照公式一次填完表格 ,.

填完后的表格如圖所示 , 在dp(4,8)的位置即為我們獲取到的最大價(jià)值.

核心思想其實(shí)就是將問題規(guī)模從大變小了而已.
有了方程式我們就可以開始寫代碼了

3 .開始編碼

首先我們獲取到的信息: 一串字符串 , 還有一行文本框的最大長(zhǎng)度。

    /**
     * 初始化輸入規(guī)模
     * 
     * @param strs      待排序的字符串
     * @param maxLength 一行文本框的長(zhǎng)度
     */
    public void init(String[] strs, int maxLength) {
        this.strs = strs;
        this.maxLength = maxLength;

        buildPairs(strs);
        caculateMaxValue();
    }

為了構(gòu)造出相對(duì)應(yīng)的模型， 我們首先對(duì)輸入進(jìn)行處理，構(gòu)造成鍵值對(duì)的形式。為了最后能表示出哪些字符唄選中，額外放置一個(gè)boolean標(biāo)記

    class Pair {
        int value;
        int weight;
        boolean choosed;
        String content;
    }


// 初始化v:w對(duì) 因?yàn)槲淖植痪哂袃r(jià)值概念 , 所以規(guī)定所有文字的平均價(jià)值相等
    private void buildPairs(String[] st) {
        this.pairs = new ArrayList<Pair>();
//      this.pairs=new Pair[st.length]; // 創(chuàng)建vw對(duì)
        for (int i = 0; i < st.length; i++) {
            Pair pair = new Pair();
            pair.value = pair.weight = st[i].length();
            pair.content = st[i];
            pair.choosed = false;
            // 保存所有的文本信息
            pairs.add(pair);
        }
    }

有了基礎(chǔ)數(shù)據(jù)后 ,我們開始寫矩陣

private void caculateMaxValue() {
        // 創(chuàng)建二維表 , 規(guī)定縱軸為pair對(duì), 橫軸為背包重量 , dp為當(dāng)前背包下當(dāng)前選擇中的最大價(jià)值
        dp = new int[strs.length + 1][maxLength + 1];

        // 第一行填充0與第一列填充0不用再寫
        // 此時(shí)從坐標(biāo)點(diǎn)(1,1)開始填寫

        for (int i = 1; i < dp.length; i++) {
            // 首先按列遍歷
            for (int j = 1; j < dp[0].length; j++) {
                // 一行一行的填寫
                if (j - pairs.get(i - 1).weight < 0) {
                    // 放不下時(shí) 沿用上一種策略
                    dp[i][j] = dp[i - 1][j];
                    pairs.get(i - 1).choosed = false;
                } else {
                    // 放得下時(shí), 比較最大值填寫
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - pairs.get(i - 1).weight] + pairs.get(i - 1).value);
                }
            }
        }

        // 輸出動(dòng)態(tài)規(guī)劃矩陣
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println("");
        }
    }

最后在main函數(shù)中調(diào)用
//01背包問題

String[] str=new String[]{"H","SX","GCX","YYWX"};
        
ZeroOnePackage dPackage=new ZeroOnePackage();
dPackage.init(str, 8);

輸出結(jié)果如圖所示

到這里結(jié)束了么?不存在的 , 這個(gè)算法只是幫我們選出了最大價(jià)值 , 并沒有拿到我們要的那些字符串 , 我們需要回溯找到解的組成

1. V(i,j)=V(i-1,j)時(shí)，說明沒有選擇第i 個(gè)商品，則回到V(i-1,j)；
2. V(i,j)=V(i-1,j-w(i))+v(i)實(shí)時(shí)，說明裝了第i個(gè)商品，該商品是最優(yōu)解組成的一部分，隨后我們得回到裝該商品之前，即回到V(i-1,j-w(i))；
3. 一直遍歷到i＝0結(jié)束為止，所有解的組成都會(huì)找到。
   這里就不演示過程了, 直接給出代碼吧

// 輸出選中的鍵值對(duì)
FindWhat(dp.length-1,dp[0].length-1);
for (Pair pair : pairs) {
    if (pair.choosed) {
        System.out.print(pair.content + " ");
    }
}

/**
     * 找到最優(yōu)解方案
     * @param i
     * @param j
     */
    void FindWhat(int i,int j)//尋找解的組成方式
    {
        if(i>=1)
        {
            if(dp[i][j]==dp[i-1][j])//相等說明沒裝
            {
                pairs.get(i-1).choosed=false;//全局變量，標(biāo)記未被選中
                FindWhat(i-1,j);
            }
            else if( j-pairs.get(i-1).weight>=0 && dp[i][j]==dp[i-1][j-pairs.get(i-1).weight]+pairs.get(i-1).value )
            {
                pairs.get(i-1).choosed=true;//標(biāo)記已被選中
                FindWhat(i-1,j-pairs.get(i-1).weight);//回到裝包之前的位置
            }
        }
    }

至此 , 問題解決

如果說有什么不完美的地方的話 , 也就是文字間距的問題了 , 給文字設(shè)置weight時(shí)加上 間距/2 即可.