力扣爆刷第76天–动态规划完全背包和多重背包
一、139.单词拆分
题目链接：https://leetcode.cn/problems/word-break/description/
思路：本题让使用单词拼接成字符串，单词可以重复使用，问能否拼接出来，要看出题目的本质，拼单词的过程类似于往背包中装东西，只不过要求顺序，和爬楼梯一样，需要顺序，故本题是一个典型的完全背包求排序，明白了这点，本题非常好做，定义dp[i]表示[0, i]可以被单词拼接，那么只要dp[i-word.length()]=true，且s.substring(i-w.length(), i) == word，即可推出dp[i]=true，从而递推公式也有了。
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(String w : wordDict) {
if(i < w.length() || dp[i] || !dp[i-w.length()]) continue;
dp[i] = isEqual(s, i, w);
}
}
return dp[s.length()];
}
boolean isEqual(String s, int index, String w) {
int i = index-w.length(), j = 0;
while(i < index) {
if(s.charAt(i) != w.charAt(j)) return false;
i++;
j++;
}
return true;
}
}
二、56. 携带矿石资源（第八期模拟笔试）
题目链接：https://kamacoder.com/problempage.php?pid=1066
思路：本题是多重背包，其实多重背包就是物品可以多次使用，但是使用的次数是有限制的，但是我们可以把物品的使用次数给摊开，都加入到一个数组里，就又变回了01背包问题了，不过直接这么做容易超时，可以采用下面的方法。
import java.lang.*;
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int c = scan.nextInt(), n = scan.nextInt();
int[] weight = new int[n];
int[] price = new int[n];
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
weight[i] = scan.nextInt();
}
for(int i = 0; i < n; i++) {
price[i] = scan.nextInt();
}
for(int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
int[] dp = new int[c+1];
for(int i = 0; i < n; i++) {
for(int j = c; 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*price[i]);
}
}
}
System.out.println(dp[c]);
}
}
