题目与题解
参考资料：背包问题总结
139.单词拆分
题目链接：139.单词拆分
代码随想录题解：139.单词拆分
解题思路：
转换为背包问题，单词数组是可以放入背包的物品，字符串是背包，单词可以无限取，所以是完全背包问题，又因为单词是有顺序的，所以该题是求排列。
但写的时候就很懵了，因为这里不是计算价值，也不是计算重量，没有办法直接将其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背包已经忘记了，复习一下。
今日收获
巩固了一下背包问题。
基础是动态规划五部曲：
- 确定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背包 / 多重背包
二维：先遍历背包或先遍历物品都可以，从小到大遍历
一维：先遍历物品后遍历背包，遍历背包时为了防止更新异常需要从大到小遍历。
完全背包：
普通问题（如求最大或最小数）：先遍历背包或先遍历物品都可以，从小到大遍历
求组合数：先遍历物品后遍历背包
求排列数：先遍历背包后遍历物品
