背包总结
听说背包问题很难？ 这篇总结篇来拯救你了
年前我们已经把背包问题都讲完了，那么现在我们要对背包问题进行总结一番。
背包问题是动态规划里的非常重要的一部分，所以我把背包问题单独总结一下，等动态规划专题更新完之后，我们还会在整体总结一波动态规划。
关于这几种常见的背包，其关系如下：
通过这个图，可以很清晰分清这几种常见背包之间的关系。
在讲解背包问题的时候，我们都是按照如下五部来逐步分析，相信大家也体会到，把这五部都搞透了，算是对动规来理解深入了。
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
其实这五部里哪一步都很关键，但确定递推公式和确定遍历顺序都具有规律性和代表性，所以下面我从这两点来对背包问题做一做总结。
#背包递推公式
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
- 动态规划：494.目标和(opens new window)
- 动态规划：518. 零钱兑换 II(opens new window)
- 动态规划：377.组合总和Ⅳ(opens new window)
- 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
#遍历顺序
#01背包
在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！
#完全背包
说完01背包，再看看完全背包。
在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
相关题目如下：
- 求组合数：动态规划：518.零钱兑换II(opens new window)
- 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)
如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：
对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。
#总结
这篇背包问题总结篇是对背包问题的高度概括，讲最关键的两部：递推公式和遍历顺序，结合力扣上的题目全都抽象出来了。
而且每一个点，我都给出了对应的力扣题目。
最后如果你想了解多重背包，可以看这篇动态规划：关于多重背包，你该了解这些！ (opens new window)，力扣上还没有多重背包的题目，也不是面试考察的重点。
如果把我本篇总结出来的内容都掌握的话，可以说对背包问题理解的就很深刻了，用来对付面试中的背包问题绰绰有余！
已解答 中等
相关标签
相关企业给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入:输出:解释:"""" 拼接成示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
func wordBreak(s string, wordDict []string) bool {
//背包：整个单词， 石头：单词集， 可重复：完全背包，是否能充满:排列问题(先背包后石头),,
//dp[i] i为长度的背包是否能装好
//递推公式，if dp[i-len(stone)] == true and s[i:j] = stone dp[i] = true
//初始化 dp[0] = true
//完全背包问题，从前到后
//输出最后一位
dp := make([]bool, len(s)+1)
dp[0] = true
for bag := 1; bag < len(s)+1; bag++ {
for stone := 0; stone < len(wordDict); stone++ {
if bag-len(wordDict[stone]) < 0 {
continue
}
if dp[bag-len(wordDict[stone])] && s[bag-len(wordDict[stone]):bag] == wordDict[stone] {
dp[bag] = true
}
}
}
return dp[len(s)]
}56. 携带矿石资源（第八期模拟笔试） 时间限制：5.000S 空间限制：256MB
题目描述
你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。
给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。
输入描述
输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。
接下来的三行，每行包含 N 个正整数。具体如下：
第二行包含 N 个整数，表示 N 种矿石的重量。
第三行包含 N 个整数，表示 N 种矿石的价格。
第四行包含 N 个整数，表示 N 种矿石的可用数量上限。
输出描述
输出一个整数，代表获取的最大价值。输入示例
10 3
1 3 4
15 20 30
2 3 2输出示例
90提示信息
数据范围：
1 <= C <= 10000;
1 <= N <= 10000;
1 <= w[i], v[i], k[i] <= 10000;
存在数组越界， karma的测试用例有问题吧
func knapsack(spaces, values, limits []int, space int) int {
//背包 容量总数， 石头， 矿石， 数据非0，1，非无限，多重背包 先后向前， 最大价格
//dp[i] ，i容量大小的包，最大价格
//递推公式， dp[i] = max(dp[i], dp[i-1*w[k]]+v[k]*1, dp[i-2*w[k]] + v[k]+2)
//初始化， dp[0]
//遍历，从后向前
dp := make([]int, space+1)
for stone := 0; stone < len(spaces); stone++ {
for bag := space; bag >= spaces[stone]; bag-- {
for limit := 1; limit <= limits[stone] && (bag-limit*spaces[stone]) >= 0; limit++ {
dp[bag] = max(dp[bag], dp[bag-limit*spaces[stone]]+limit*values[stone])
}
}
}
return dp[space]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
var m, n int
fmt.Scan(&m, &n)
materialSpaces := make([]int, n)
inputs := bufio.NewScanner(os.Stdin)
inputs.Scan() //每次读入一行
data := strings.Split(inputs.Text(), " " ) //通过空格将他们分割，并存入一个字符串切片
for i := range data {
val, _ := strconv.Atoi(data[i]) //将字符串转换为int
materialSpaces[i] = val
}
inputs.Scan()
materialValues := make([]int, n)
data = strings.Split(inputs.Text(), " " ) //通过空格将他们分割，并存入一个字符串切片
for i := range data {
val, _ := strconv.Atoi(data[i]) //将字符串转换为int
materialValues[i] = val
}
inputs.Scan()
materialLimit := make([]int, n)
data = strings.Split(inputs.Text(), " " ) //通过空格将他们分割，并存入一个字符串切片
for i := range data {
val, _ := strconv.Atoi(data[i]) //将字符串转换为int
materialLimit[i] = val
}
res := knapsack(materialSpaces, materialValues, materialLimit, m)
fmt.Println(res)
}