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

看不懂

valid数组为什么长度是s.length()+1

完全背包的排列问题。

字符串是背包，字典单词是物品，看字典单词是否可以填充完背包。

先遍历背包再遍历物品

代码随想录

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;
        for(int i = 1; i <= s.length(); i++) {//背包
            for(int j = 0; j < i && !valid[i]; j++) {//物品
                if(set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }
        return valid[s.length()];
    }
}

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

代码随想录

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

可以等代成01背包问题。将重复的物品看成单独的物品。

?背包问题总结篇！?

代码随想录

递推公式：

最大价值：dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);

最大容量：dp[j] = Math.max(dp[j], dp[j-weight[i]] + weight[i]);

方法数：dp[j] += dp[j-weight[i]];

最大子集个数：dp[j] = Math.max(dp[j], dp[j-weight[i]] + 1);