第四十六天| 139.单词拆分、卡码网 56. 携带矿石资源（同多重背包问题）

本文主要是介绍第四十六天| 139.单词拆分、卡码网 56. 携带矿石资源（同多重背包问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 139.单词拆分

题目链接：139 单词拆分

题干：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

思考：动态规划。由于本题字典中的字符串可多次选取，因此本题为完全背包的类似问题。

确定dp数组以及下标的含义

dp[i] : 在字典中任选，从字符串s首部拼出i个字符是否成功

确定递推公式

从dp[i]的定义可以看出，每次从字典中选取字符串wordDict[ j ] 都往前比较，若相同且dp[ i - wordDict[ j ].size()]为true，则此为可从dp[ i - wordDict[ j ].size()]后拼接wordDict[ j ]实现dp[i]的匹配

因此递推公式为：dp[i] = dp[i] || dp[i - wordDict[j].size()]。

dp数组如何初始化

从递推公式中可以看出，dp[i] 的状态依靠 dp[i - wordDict[j].size()]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都是false。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

前提：如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

本题其实我们求的是排列数。拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

"apple", "pen" 是物品，那么我们要求物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。

"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是先遍历背包（字符串），再遍历物品（字典）。

举例推导dp[i]

举例: s = "leetcode", wordDict = ["leet", "code"]，dp状态如图：

代码：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size() + 1, false);       //dp[i]表示在字典中任选，从字符串s首部拼出i个字符是否成功dp[0] = true;for (int i = 1; i <= s.size(); i++)         //遍历字符串for (int j = 0; j < wordDict.size(); j++)  //遍历字典if (wordDict[j].size() <= i && s.substr(i - wordDict[j].size(), wordDict[j].size()) == wordDict[j])        //选取子串比较dp[i] = dp[i] || dp[i - wordDict[j].size()];        //递推公式return dp[s.size()];}
};

卡码网 56. 携带矿石资源

题目链接：56 携带矿石资源

题干：你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述：

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。

接下来的三行，每行包含 N 个正整数。具体如下：

第二行包含 N 个整数，表示 N 种矿石的重量。

第三行包含 N 个整数，表示 N 种矿石的价格。

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述：

输出一个整数，代表获取的最大价值。

思考：此题就是多重背包换个描述方式。与01背包非常相似。其中的难点在于不同类型的物品（矿石）有不同的数量，那将如果把每件物品摊开，其实就是一个01背包问题。因此在遍历前先处理物品，代码如下：

for (int i = 0; i < n; i++) {while (nums[i] > 1) { // 物品数量不是一的，都展开weight.push_back(weight[i]);value.push_back(value[i]);nums[i]--;}}

然而如果物品数量很多的话，C++中，这种操作十分费时，主要消耗在vector的动态底层扩容上。（其实这里也可以优化，先把所有物品数量都计算好，一起申请vector的空间。

但此外还有其他方式，把同一种类的物品放在一块遍历即将每种商品遍历的个数放在01背包里面在遍历一遍。

代码：

#include<iostream>
#include<vector>
using namespace std;//采用滚动数组存储的最大价值
int multipleKnapsack(const vector<int>& weight, const vector<int>& value, vector<int> nums, int bagWeight) {//dp[j]表示背包空间为j的情况下，从所有物品里任取，能达到的最大价值vector<int> dp(bagWeight + 1, 0);for (int i = 0; i < weight.size(); i++)     //遍历物品for (int j = bagWeight; j >= weight[i]; j--)     //遍历背包重量for (int k = 1; k <= nums[i] && j >= k * weight[i]; k++)     //遍历数量dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);return dp[bagWeight];  
}int main() {int bagWeight, objectNum;cin >> bagWeight >> objectNum;vector<int> weight(objectNum);vector<int> value(objectNum);vector<int> nums(objectNum);for (int i = 0; i < objectNum; i++)cin >> weight[i];for (int i = 0; i < objectNum; i++)cin >> value[i];for (int i = 0; i < objectNum; i++)cin >> nums[i];cout << multipleKnapsack(weight, value, nums, bagWeight) << endl;system("pause");
}

背包问题总结：

首先将各种背包问题汇聚成一张图来看：