代码随想录算法训练营第四十六天| 139.单词拆分，关于多重背包，你该了解这些！， 背包问题总结篇！

本文主要是介绍代码随想录算法训练营第四十六天| 139.单词拆分，关于多重背包，你该了解这些！， 背包问题总结篇！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题目与题解

参考资料：背包问题总结

139.单词拆分

题目链接：139.单词拆分

代码随想录题解：139.单词拆分

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili

解题思路：

        转换为背包问题，单词数组是可以放入背包的物品，字符串是背包，单词可以无限取，所以是完全背包问题，又因为单词是有顺序的，所以该题是求排列。

        但写的时候就很懵了，因为这里不是计算价值，也不是计算重量，没有办法直接将其value相加，不知道该咋写，只能看答案。

看完代码随想录之后的想法 

        首先还是要明确，dp的含义一般就是题目要求的结果。所以这题，dp数组表示当字符串长度为dp[i]时，是否存在符合条件的单词组合，存在则为true。

        由于是排列，所以应该先遍历背包（i），后遍历物品（j），递推公式为：当dp[j]为true，表示字符串长度为j时存在单词组合，所以只需要查询substr(j,i)的子字符串是否在单词数组中存在，存在则将当前dp[i]置为true。

        初始化dp[0]必须为true，否则dp计算出来永远为false。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for (int i = 1; i < dp.length; i++) {for (int j = 0; j < i; j++) {String substr = s.substring(j, i);if (dp[j] && wordDict.contains(substr)) {dp[i] = true;break;}}}return dp[s.length()];}
}

遇到的困难

        dp的定义一开始没有理清楚，虽然知道是完全背包的排列问题，但是没有想到用子字符串作为计算的方法。好难。

关于多重背包，你该了解这些！

题目链接：关于多重背包，你该了解这些！

代码随想录题解：关于多重背包，你该了解这些！

解题思路：

        多重背包就是01背包的升级版，只要把多个重量和价值相同的物品当作01背包里面多个不同的物品就可以了，同样用01背包的思路来做，只不过遍历的时候要多加一个对物品数量的遍历。

public class ID56Kama {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int C = scanner.nextInt();int N = scanner.nextInt();int[] w = new int[N];int[] v = new int[N];int[] k = new int[N];for (int i = 0; i < N; i++) {w[i] = scanner.nextInt();}for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();}for (int i = 0; i < N; i++) {k[i] = scanner.nextInt();}int[] dp = new int[C+1];for (int i = 0; i < N; i++) {for (int k1 = 0; k1 < k[i]; k1++) {for (int j = C; j >= w[i]; j--) {dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);}}}System.out.println(dp[C]);}
}

看完代码随想录之后的想法 

        随想录计算时用相乘代替累加，本质是一样的。

import java.util.Scanner;
class multi_pack{public static void main(String [] args) {Scanner sc = new Scanner(System.in);/*** bagWeight:背包容量* n:物品种类*/int bagWeight, n;//获取用户输入数据，中间用空格隔开，回车键换行bagWeight = sc.nextInt();n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] nums = new int[n];for (int i = 0; i < n; i++) weight[i] = sc.nextInt();for (int i = 0; i < n; i++) value[i] = sc.nextInt();for (int i = 0; i < n; i++) nums[i] = sc.nextInt();int[] dp = new int[bagWeight + 1];//先遍历物品再遍历背包，作为01背包处理for (int i = 0; i < n; i++) {for (int j = bagWeight; j >= weight[i]; j--) {//遍历每种物品的个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}System.out.println(dp[bagWeight]);}
}

遇到的困难

        01背包已经忘记了，复习一下。

今日收获

        巩固了一下背包问题。

        基础是动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

        背包问题常见的递归公式有以下几种：

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

• 动态规划：416.分割等和子集(opens new window)
• 动态规划：1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法：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]); ，对应题目如下：

• 动态规划：474.一和零(opens new window)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

• 动态规划：322.零钱兑换(opens new window)
• 动态规划：279.完全平方数

遍历顺序

01背包 / 多重背包

        二维：先遍历背包或先遍历物品都可以，从小到大遍历

        一维：先遍历物品后遍历背包，遍历背包时为了防止更新异常需要从大到小遍历。

完全背包：

        普通问题（如求最大或最小数）：先遍历背包或先遍历物品都可以，从小到大遍历

        求组合数：先遍历物品后遍历背包

        求排列数：先遍历背包后遍历物品

这篇关于代码随想录算法训练营第四十六天| 139.单词拆分，关于多重背包，你该了解这些！， 背包问题总结篇！的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---