背包问题 LeetCode
0-1背包问题
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大。
使用一维数组更为简洁。
0-1背包和完全背包唯一不同就是体现在遍历顺序上，从一维数组看，第二个遍历过程0-1是从后往前，完全背包是从前往后
package leetcode;
import java.util.Arrays;
public class BagDemo {
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
// 物品的数量
int num = weight.length;
// 背包容量
int vol = 4;
int[][] dp = new int[num][vol + 1];
// 初始化dp数组, 第一行从背包容量等于物品质量开始，剪枝
for (int j = weight[0]; j <= vol; j++) {
dp[0][j] = value[0];
}
// 遍历行，即先遍历物品，数量从小到多
for (int i = 1; i < num; i++) {
// 再遍历列，即遍历容量，从小到大
for (int j = 1; j <= vol; j++) {
// 如果当前背包容量小于当前物品重量，无法放入，
// 最大值等于不放这个物品的最大值：
if (j < weight[i]) {
// [i - 1]等于不放这个物品的重量
dp[i][j] = dp[i - 1][j];
} else {
// 如果放进去：相当于容量为j - i的背包的dp值加上当前i的价值；
int isPut = dp[i - 1][j - weight[i]] + value[i];
int noPut = dp[i - 1][j];
// 两种情况取最大值
dp[i][j] = Math.max(isPut, noPut);
}
}
}
System.out.println(dp[num - 1][vol]);
System.out.println(Arrays.deepToString(dp));
}
}
class BagDemo1 {
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
// 物品的数量
int num = weight.length;
// 背包容量
int vol = 4;
int[] dp = new int[vol + 1];
for (int i = 0; i < num; i++) {
// 从后向前，前面的数字不会受影响；
for (int j = vol; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
System.out.println(Arrays.toString(dp));
}
}
}
LeetCode题解
/**
* 139. 单词拆分
*/
// 自己写出来的复杂度比官方解答小，逻辑更细节一些，还是有点蒙
class Solution99 {
public boolean wordBreak(String s, List<String> wordDict) {
String[] word = wordDict.toArray(new String[0]);
char[] str = s.toCharArray();
boolean[] dp = new boolean[str.length + 1];
dp[0] = true;
// 字符串组合是无序的，所以要遍历背包容量，再遍历物品
for (int j = 0; j <= str.length; j++) {
for (String w : word) {
// 边界确实有点懵逼，left和right
if (j >= w.length() && isTrue(str, w, j - w.length(), j))
dp[j] |= dp[j - w.length()];
}
}
return dp[str.length];
}
public boolean isTrue(char[] str, String word, int left, int right) {
int j = 0;
for (int i = left; i < right; i++, j++) {
if (str[i] != word.charAt(j)) return false;
}
return true;
}
}
/**
* 279. 完全平方数
*/
class Solution98 {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for (int i = 0; i * i <= n; i++) {
for (int j = i * i; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}
/**
* 322. 零钱兑换
*/
class Solution97 {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int maxValue = amount + 1;
Arrays.fill(dp, maxValue);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] != maxValue ? dp[amount] : -1;
}
}
class Solution96 {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int j = 1; j <= amount; j++) {
for (int coin : coins) {
if (j >= coin) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
return dp[amount] > amount ? dp[amount] : -1;
}
}
/**
* 70. 爬楼梯 (进阶)
* 完全背包问题
*
* @date 2021 11 15
*/
class Solution95 {
public int climbStairs(int n) {
int[] value = new int[]{1, 2};
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 0; i <= n; i++) {
for (int v : value) {
if (i >= v) {
dp[i] += dp[i - v];
}
}
}
return dp[n];
}
}
/**
* 377. 组合总和 Ⅳ
*
* @date 2021 11 14
*/
class Solution94 {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 0; j <= target; j++) {
for (int num : nums) {
if (num <= j) {
dp[j] += dp[j - num];
}
}
}
return dp[target];
}
}
/**
* 518. 零钱兑换 II
*/
class Solution93 {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
}
/**
* 474. 一和零
*/
// 二维背包问题，唉，懵逼
class Solution92 {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
// 初始值，相当于什么都不拿，价值为0，可以忽略不写；
for (String str : strs) {
// 找出当前元素的0,1个数，相当于找出当前物品的质量
int sum0 = 0, sum1 = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
sum0++;
} else sum1++;
}
// 二维背包的重量，两重for循环遍历取得最大值
for (int i = m; i >= sum0; i--) {
for (int j = n; j >= sum1; j--) {
// 当前物品的价值为一；
dp[i][j] = Math.max(dp[i - sum0][j - sum1] + 1, dp[i][j]);
}
}
}
return dp[m][n];
}
}
/**
* 494. 目标和
*/
class Solution91 {
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if (Math.abs(target) > sum || (sum + target) % 2 != 0) return 0;
int vol = (sum + target) / 2;
int[] dp = new int[vol + 1];
// dp的值代表着方法总数。初始值为1
dp[0] = 1;
for (int num : nums) {
for (int j = vol; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[vol];
}
}
/**
* 1049. 最后一块石头的重量 II
* 2021 11 13
*/
// 使用boolean数组，速度更快
// dp[j] = true 此时的j即为能取到的最大值
class Solution90 {
public int lastStoneWeightII(int[] stones) {
int sum = Arrays.stream(stones).sum();
int vol = sum / 2;
int[] dp = new int[vol + 1];
for (int stone : stones) {
for (int j = vol; j >= stone; j--) {
dp[j] = Math.max(dp[j], dp[j - stone] + stone);
}
}
return sum - dp[vol];
}
}
/**
* 416. 分割等和子集
*/
// 官方解答，使用boolean数组
class Solution89 {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; --j) {
dp[j] |= dp[j - num];
}
}
return dp[target];
}
}
// 巧妙的转化成背包问题
class Solution88 {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
// 限定背包容量，所得的子集和只会小于等于sum / 2；
int vol = sum / 2;
int[] dp = new int[vol + 1];
for (int i = 0; i < nums.length; i++) {
for (int j = vol; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[vol] == vol;
}
}