单词拆分

题目：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路：字符串s就是我们的背包，wordDict就是物品，我们要从物品中选出有序的字符串拼接成目标字符串s

• dp[i]的含义：对于长度为i的字符串，能否在字典中找出字符串拼接成目标的字符串s的值为dp[i]
• 递推公式：if(wordDict.contains(substring(j,i) && dp[j]) dp[i] = true
  
• dp数组的初始化：dp[0] = true
• 遍历顺序：因为求排列，所有是先遍历背包，后遍历物品
• 打印dp数组

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]表示：字符串长度为i对字符串 能否拼接出s的值为dp[i]
        boolean[] dp = new boolean[s.length()+1];
        // 初始化
        dp[0] = true;
        for(int i = 1;i<=s.length();i++){// 背包
            for(int j = 0;j<i;j++){// 物品 这里为什么是 j<i，因为字符串的长度就是i，不能大于i，大于i了就没有一样
                String str = s.substring(j,i);
                if(wordDict.contains(str) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

多重背包

什么是多重背包？
就是在0-1背包的基础上增加了物品数量的限制，也就是说，现在有容量为bagSize的背包容量和一些物品，这个物品的属性有重量、价值和数量，然后求背包能够装的最大价值是多少

思路：我们可以把物品数量大于1的物品展开，也就是在增加一个相同的重量和价值的物品，这样当前的问题也就变成了0-1背包的问题了

• dp[j]的含义：背包容量为i的最大价值为dp[j]
• 递推公式：dp[j] = Math.max(dp[j],dp[j-weigth[i]]+value[i])
• dp数组初始化：dp[0]=0
• 遍历顺序：先背包，后物品
• 打印dp数组

public static void main(String[] args) {
        Test test = new Test();
        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));
        System.out.println(test.multiPack(weight, value, nums, 10));
    }

    /**
     * 多重背包
     *
     * @param weight  物品重量
     * @param value   物品价值
     * @param nums    物品数量
     * @param bagSize 背包容量
     * @return 背包能够装的最大价值
     */
    private int multiPack(List<Integer> weight, List<Integer> value, List<Integer> nums, int bagSize) {
        // 把物品展开
        for (int i = 0; i < nums.size(); i++) {
            while (nums.get(i) > 1) {
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i, nums.get(i) - 1);
            }
        }
        // 0-1背包
        int[] dp = new int[bagSize + 1];
        dp[0] = 0;
        for (int i = 0; i < weight.size(); i++) {// 物品
            for (int j = bagSize; j >= weight.get(i); j--) {// 背包
                dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
            }
        }
        return dp[bagSize];
    }

还有一种方式就是在0-1背包的基础上增加遍历个数

public static void main(String[] args) {
        Test test = new Test();
        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));
        System.out.println(test.multiPack(weight, value, nums, 10));
    }

    /**
     * 多重背包
     *
     * @param weight  物品重量
     * @param value   物品价值
     * @param nums    物品数量
     * @param bagSize 背包容量
     * @return 背包能够装的最大价值
     */
    private int multiPack(List<Integer> weight, List<Integer> value, List<Integer> nums, int bagSize) {
        int[] dp = new int[bagSize + 1];
        dp[0] = 0;
        for (int i = 0; i < weight.size(); i++) {// 物品
            for (int j = bagSize; j >= weight.get(i); j--) {// 背包
                // 增加遍历个数
                // k<=nums.get(i)是因为物品只有nums.get(i)多个
                // j-k*weight.get(i) >= 0 是判断当前的背包能不能放的下k个物品i
                for (int k = 1; k <= nums.get(i) && (j - k * weight.get(i)) >= 0; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight.get(i)] + k * value.get(i));
                }
            }
        }
        return dp[bagSize];
    }