代码随想录算法训练营day46 | 139.单词拆分 ，多重背包，背包问题总结篇！

---

139.单词拆分

教程视频：https://www.bilibili.com/video/BV1pd4y147Rh

解法一：动态规划（不好想）

思路：
1、dp[j]含义：是否可以拼接出至字符串的 i 个字符（本可以使用boolean数组，这里使用int数组0表示不可以，1表示可以）
2、递推公式：

if(wordDict.contains(s.substring(i,j)) && dp[i]==1){
	dp[j]=1;
}
1
2
3

3、dp数组初始化：为满足递推需要dp[0]=1;其余下标在迭代过程中会被判断，初始化为0
4、遍历顺序：每个单词可以使用多次，且输出结果与单词顺序有关，完全背包问题求排列。外层for循环正向遍历背包容量，内层for循环遍历物品。
5、打印验证：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int[] dp=new int[s.length()+1];
        dp[0]=1;
        //需要匹配排列（先正序遍历背包容量再遍历物品）
        for(int j=1;j<=s.length();j++){
            for(int i=0;i<j;i++){
                if(wordDict.contains(s.substring(i,j)) && dp[i]==1){
                    dp[j]=1;
                }
            }
        }
        return dp[s.length()]==1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法二：回溯+记忆化

class Solution {
    private int[] memo;//记录状态，用于剪枝
    private List<String> wordDictField;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        wordDictField = wordDict;
        return backtracking(s, 0);
    }

    //输入为字符串及起始索引，输出是否能完全拼接
    public boolean backtracking(String s, int startIndex) {
        // System.out.println(startIndex);
        //终止条件：到达字符串末尾
        if (startIndex == s.length()) {
            return true;
        }
        //剪枝：如果前面已经验证从startIndex开始不能成功拼接，直接结束递归
        if (memo[startIndex] == -1) {
            return false;
        }

        for (int i = startIndex; i < s.length(); i++) {
            String sub = s.substring(startIndex, i + 1);
	        // 拆分出来的单词无法匹配
            if (!wordDictField.contains(sub)) {
                continue;                
            }
            boolean res = backtracking(s, i + 1);
            if (res) return true;
        }
        // 这里是回溯
        // 找遍了startIndex~s.length()也没能完全匹配，标记从startIndex开始不能找到
        memo[startIndex] = -1;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

多重背包

问题描述：有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包可以转化为01背包，每件物品最多有Mi件可用，把Mi件摊开，就是一个01背包问题了。该解法时间复杂度为O(m × n × k)，其中 m：物品种类个数，n背包容量，k单类物品数量

解法一：转化为01背包

public void testMultiPack1(){
    // 版本一：改变物品数量为01背包格式
    List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
    List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
    List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
    int bagWeight = 10;

    for (int i = 0; i < nums.size(); i++) {
        while (nums.get(i) > 1) { // 把物品展开为i
            weight.add(weight.get(i));
            value.add(value.get(i));
            nums.set(i, nums.get(i) - 1);
        }
    }

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
        }
        System.out.println(Arrays.toString(dp));
    }
}

public void testMultiPack2(){
    // 版本二：改变遍历个数
    int[] weight = new int[] {1, 3, 4};
    int[] value = new int[] {15, 20, 30};
    int[] nums = new int[] {2, 3, 2};
    int bagWeight = 10;

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            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(Arrays.toString(dp));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

背包问题总结

递推公式

遍历顺序