本文主要是介绍第四十六天| 139.单词拆分、卡码网 56. 携带矿石资源（同多重背包问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode 139.单词拆分
题目链接：139 单词拆分
题干：给你一个字符串
s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和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");
}背包问题总结：
首先将各种背包问题汇聚成一张图来看：
由上图可以清晰的看出各类背包问题的关系。
背包问题都可以按照如下五部来逐步分析。
-
确定dp数组（dp table）以及下标的含义
-
确定递推公式
-
dp数组如何初始化
-
确定遍历顺序
-
举例推导dp数组
每一步都很重要，但确定递推公式和确定遍历顺序都具有规律性和代表性。下面从这两步总结。
-
01背包
在01背包中，理清: 二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。而一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的。
- 完全背包
在完全背包中，理清纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
- 多重背包
本篇中，理清多重背包只需要将各种物品的数量拆开看作是一个一个的物品，便成了01背包问题。
- 对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解。
这篇关于第四十六天| 139.单词拆分、卡码网 56. 携带矿石资源（同多重背包问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
