代码随想录 Day42 - 动态规划（三）

作者：jjn0703

2023-08-13
江苏
本文字数：1265 字
阅读完需：约 4 分钟

背包问题总览

如下图，备战面试，重点是 01 背包，完全背包，多重背包了解即可。

01 背包问题（二维数组）

步骤一：确认 dp 数组及下标的含义
dp[i][j]表示从下标为[0,i]的物品中，选取任意的物品并放入容量为 j 的背包的价值总和。
步骤二：确认递推公式
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
步骤三：初始化 dp 数组
步骤四：确定遍历顺序
两层 for 循环，先遍历物品或者背包重量都可以，正向遍历
步骤五：举例推导

01 背包问题（一维数组）

步骤一：确认 dp 数组及下标的含义
dp[j]表示容量为 j 的背包所背物品的最大价值。
步骤二：确认递推公式
dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
步骤三：初始化 dp 数组
步骤四：确定遍历顺序
先遍历物品再遍历背包，不可以颠倒顺序
步骤五：举例推导

416. 分割等和子集

此题需要特殊处理一下异常情况，如某个数超过总和一半。

二维数组解法：

package jjn.carl.dp;
/** * @author Jiang Jining * @since 2023-08-13 9:40 */public class LeetCode416 {    public boolean canPartition(int[] nums) {        int sum = 0;        int max = nums[0];        for (int num : nums) {            sum += num;            max = Math.max(max, num);        }        if (sum % 2 == 1) {            return false;        }        int target = sum / 2;        if (max > target) {            return false;        }        boolean[][] dp = new boolean[nums.length][target + 1];        for (int i = 0; i < nums.length; i++) {            dp[i][0] = true;        }        dp[0][nums[0]] = true;        for (int i = 1; i < nums.length; i++) {            int num = nums[i];            for (int j = 1; j <= target; j++) {                if (j >= num) {                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];                } else {                    dp[i][j] = dp[i - 1][j];                }            }        }        return dp[nums.length - 1][target];    }}

复制代码

一维数组解法：

package jjn.carl.dp;
/** * @author Jiang Jining * @since 2023-08-13 15:21 */public class LeetCode416_2 {    public boolean canPartition(int[] nums) {        int sum = 0;        int maxNum = nums[0];        for (int num : nums) {            sum += num;            maxNum = Math.max(maxNum, num);        }        if (sum % 2 == 1) {            return false;        }        int target = sum / 2;        if (maxNum > target) {            return false;        }        boolean[] dp = new boolean[target + 1];        dp[0] = true;        for (int i = 0; i < nums.length; i++) {            for (int j = target; j >= nums[i]; j--) {                dp[j] = dp[i - nums[j]] || dp[j];            }        }        return dp[target];    }}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/c5ebbbf277476bc8fc790848e】。

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

发布

暂无评论

创作场景

代码随想录 Day42 - 动态规划（三）

背包问题总览

01 背包问题（二维数组）

01 背包问题（一维数组）

416. 分割等和子集

jjn0703

评论