摘要

• 如何選取物品有時(shí)也會(huì)影響代碼的執(zhí)行效率，雖然不同的選取物品的方法的時(shí)間復(fù)雜度可能在同一個(gè)數(shù)量級(jí)，但有時(shí)候執(zhí)行效率依然有比較明顯的差距。比如判斷一個(gè)字符串的一個(gè)子串是否是存在于詞典中的單詞，先枚舉子串判斷再判斷該子串是否存在于詞典中效率更高，而先枚舉詞典中的單詞再判斷單詞是否與該子串相等則效率較低。
• 多重背包問(wèn)題和 0-1 背包問(wèn)題類(lèi)似，可以簡(jiǎn)單地轉(zhuǎn)化為 0-1 背包問(wèn)題。

LeetCode139 單詞拆分

139. 單詞拆分 - 力扣（Leetcode）

• 本題也可以用完全背包的思路來(lái)理解，”物品“是字典中的單詞，”背包“是用單詞拼接出的字符串。這道題目不關(guān)心物品的價(jià)值和重量，只關(guān)心背包中特定的”物品”排列，所以，只需要保存這樣的排列是否存在的狀態(tài)信息就可以了。
• dp數(shù)組及下標(biāo)的含義：dp[j]表示從下標(biāo)0開(kāi)始，長(zhǎng)度為j的s的子串是否能被wordDict中的單詞拼接出來(lái)。
• 確定狀態(tài)轉(zhuǎn)移方程，dp[j]的值按以下規(guī)則更新
  • 假設(shè)當(dāng)前遍歷到的s的子串長(zhǎng)度為j，當(dāng)前嘗試放入wordDict[i]，如果放入wordDict[i]之前的部分能被拼接出來(lái)即dp[j - wordDict[i].size()] == true，且wordDict[i]能填入剩下的部分，即s.substr(k, j - k) == wordDict，則說(shuō)明長(zhǎng)度為j的s的子串也能被拼接出來(lái)。
  • s長(zhǎng)度為0的子串不需要使用字典中的單詞拼接，dp[0]初始化為true，便于更新dp數(shù)組

初見(jiàn)題目的題解代碼，還需要改進(jìn)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;

        for (int j = 1; j <= s.size(); j++) {
            for (int i = 0; i < wordDict.size(); i++) {
                for (int k = 0; k <= j; k++) {
                    if (j < wordDict[i].size()) break;
                    string word = s.substr(k, j - k);
                    if (word == wordDict[i] && dp[j - wordDict[i].size()]) 
                        dp[j] = dp[j - wordDict[i].size()];
                }
            }
        }

        return dp[s.size()];
    }
};

• 判斷當(dāng)前選定的wordDict[i]能不能填入s的對(duì)應(yīng)位置，其實(shí)也是判斷對(duì)應(yīng)位置的s的子串是否在wordDict中，而后者可以使用set來(lái)判斷。
• 使用set來(lái)存儲(chǔ)wordDict，先枚舉s未拼接部分的可能子串，再用set來(lái)判斷該子串是否在wordDict中，使用了哈希表，效率要比先選定wordDict[i]再枚舉s的子串要高。
• 判斷能拼接到這個(gè)位置的wordDict[i]是否存在；嘗試所有wordDict[i]，尋找是否有能拼接到這個(gè)位置的word。這兩個(gè)說(shuō)法看似相同，但前者對(duì)應(yīng)的代碼判斷元素是否存在是哈希法的優(yōu)勢(shì)，可以用空間換時(shí)間。而且初見(jiàn)時(shí)的代碼中會(huì)多次進(jìn)行比對(duì)字符串的操作，也十分影響效率。

使用set來(lái)優(yōu)化判斷是否能拼接的過(guò)程

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;

        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        for (int j = 1; j <= s.size(); j++) {
            
            for (int k = 0; k <= j; k++) {
                string word = s.substr(k, j - k);
                if (wordSet.count(word) && dp[j - word.size()]) 
                    dp[j] = dp[j - word.size()];
            }
            
        }

        return dp[s.size()];
    }
};

多重背包問(wèn)題

有 種物品和一個(gè)容量為 的背包。第 種物品最多有 件可用，每件耗費(fèi)的空間是 ，價(jià)值是 。

求解將哪些物品裝入背包可使這些物品的耗費(fèi)的空間總和不超過(guò)背包容量，且價(jià)值總和最大。

• 多重背包和 0-1 背包是非常像的，每件物品最多有 件可用，把 件攤開(kāi)，其實(shí)就是一個(gè) 0-1 背包問(wèn)題了。
• 例如以下問(wèn)題

背包最大重量為10。

物品信息如下表

• 把每種物品的數(shù)量攤開(kāi)，轉(zhuǎn)變?yōu)槿缦聠?wèn)題

• 每件物品只能用一次，那實(shí)際上就是 0-1 背包問(wèn)題。

• 為什么完全背包不能”攤開(kāi)“成 0-1 背包呢？完全背包每種物品都能無(wú)限多次選取，無(wú)限多件，當(dāng)然是”攤不開(kāi)“的。

• 第一種方案，將物品提前攤開(kāi)
• 第二種方案，在 0-1 背包的基礎(chǔ)上再遍歷每種物品的個(gè)數(shù)

測(cè)試代碼如下

// multiBag.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開(kāi)始并結(jié)束。
//

#include <iostream>
#include <vector>
using namespace std;

class testcase {
    vector<int> weight;
    vector<int> value;
    vector<int> nums;
    int bagWeight;
public:
    testcase(vector<int> weight, vector<int> value, vector<int> nums, int bagWeight) {
        this->weight = weight;
        this->value = value;
        this->nums = nums;
        this->bagWeight = bagWeight;
    }

    void test1() {
        vector<int> weight = this->weight;
        vector<int> value = this->value;
        vector<int> nums = this->nums;
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展開(kāi)
                weight.push_back(weight[i]);
                value.push_back(value[i]);
                nums[i]--;
            }
        }

        vector<int> dp(bagWeight + 1, 0);
        for (int i = 0; i < weight.size(); i++) { // 遍歷物品
            for (int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
            for (int j = 0; j <= bagWeight; j++) {
                cout << dp[j] << " ";
            }
            cout << endl;
        }
        cout << "result: " << dp[bagWeight] << endl;
    }

    void test2() {
        vector<int> dp(bagWeight + 1, 0);

        for (int i = 0; i < weight.size(); i++) { // 遍歷物品
            for (int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
                // 外面兩層循環(huán)為01背包，然后加一個(gè)循環(huán)遍歷物品的個(gè)數(shù)
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍歷個(gè)數(shù)
                    dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
            for (int j = 0; j <= bagWeight; j++) {
                cout << dp[j] << " ";
            }
            cout << endl;
        }
        cout << "result: " <<  dp[bagWeight] << endl;
    }
};

int main()
{
    testcase t1({ 1, 3, 4 }, { 15, 20, 30 }, { 2, 3, 2 }, 10);
    t1.test1();
    cout << endl << "==============\n" << endl;
    t1.test2();
}