当前位置： 首页 > news >正文

动态规划算法专题（八）：01 背包问题

news 2024/10/24 8:26:13

目录

1. 01背包【模版】

1.1 算法原理

1.2 算法代码 

1.3 空间优化版本

1.4 空间优化版本代码

2. 分割等和子集

2.1 算法原理 

2.2 算法代码

3. 目标和

3.1 算法原理 

3.2 算法代码

4. 最后一块石头的重量 II 

4.1 算法原理 

4.2 算法代码

1. 01背包【模版】

【模板】01背包_牛客题霸_牛客网

1.1 算法原理

  • 状态表示:

1) dp[i][j]：从前i个物品中挑选，总体积 不超过j 的所有挑法中，最大价值
2) dp[i][j]：从前i个物品中挑选，总体积 恰好等于j 的所有挑法中，最大价值

  • 状态转移方程:

1) 第一问

不选物品i --> dp[i-1][j]
选物品i --> j-v(i) >= 0 --> dp[i-1][j-v(i)]+w(i)

dp[i][j]=max(dp[i-1][j], dp[i-1][j-v(i)]+w(i))

2) 第二问

(在使用前面的状态时，都应该判断一下前面的状态是否能凑到, 若不能凑到则dp[i][j] == -1)

不选物品i --> dp[i-1][j]
选物品i --> j-v(i) >= 0 && dp[i-1][j-v(i)] != -1 --> dp[i-1][j-v(i)]+w(i)

(必须在前面选时，凑出j-v(i)的体积)

  • 初始化：

1) 第一问

没有物品 --> 第一行初始化为0； 容量为0 --> 第一列初始化为0

2) 第二问

dp[0][0] = 0;// 没有物品, 但是书包的容量也为0

dp[0][1~V] = -1;// 没有物品, 凑不满书包的容量

dp[1~n][0] = 0;

  • 建表顺序：

从上往下每一行，
从左往右每一列

  • 返回值：

dp[n][V]

1.2 算法代码 

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt(), V = in.nextInt();int[] arrV = new int[n + 1];int[] arrW = new int[n + 1];int x = 1;while (x <= n) { // 注意 while 处理多个 casearrV[x] = in.nextInt();arrW[x] = in.nextInt();x++;}int[][] dp1 = new int[n + 1][V + 1];for(int i = 1; i <= n; i++) {for(int j = 1; j <= V; j++) {dp1[i][j] = dp1[i - 1][j];if(j - arrV[i] >= 0) dp1[i][j] = Math.max(dp1[i][j], dp1[i - 1][j - arrV[i]] + arrW[i]);}}int[][] dp2 = new int[n + 1][V + 1];Arrays.fill(dp2[0], -1);dp2[0][0] = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= V; j++) {dp2[i][j] = dp2[i - 1][j];if(j - arrV[i] >= 0 && dp2[i - 1][j - arrV[i]] != -1) dp2[i][j] = Math.max(dp2[i][j], dp2[i - 1][j - arrV[i]] + arrW[i]);}}System.out.println(dp1[n][V]);if(dp2[n][V] != -1) System.out.println(dp2[n][V]);else  System.out.println(0);}
}

1.3 空间优化版本

dp表中的元素, 依赖于其上一行中的数据, 所以我们可以进行空间优化, 将二维的dp表优化成一维的dp表.

注意: 由于每个元素依赖的是其上一行同一列以及上一行左列的值, 所以优化时应从左往右建表.

并且, 在优化空间时, 也会对时间进行常数级别的优化. 

1.4 空间优化版本代码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt(), V = in.nextInt();int[] arrV = new int[n + 1];int[] arrW = new int[n + 1];int x = 1;while (x <= n) { // 注意 while 处理多个 casearrV[x] = in.nextInt();arrW[x] = in.nextInt();x++;}int[] dp1 = new int[V + 1];for(int i = 1; i <= n; i++) {for(int j = V; j >= arrV[i]; j--) {dp1[j] = dp1[j];dp1[j] = Math.max(dp1[j], dp1[j - arrV[i]] + arrW[i]);}}int[] dp2 = new int[V + 1];// 初始化Arrays.fill(dp2, -1);dp2[0] = 0;for(int i = 1; i <= n; i++) {for(int j = V; j >= arrV[i]; j--) {dp2[j] = dp2[j];if(dp2[j - arrV[i]] != -1) dp2[j] = Math.max(dp2[j], dp2[j - arrV[i]] + arrW[i]);}}System.out.println(dp1[V]);System.out.println(dp2[V] == -1 ? 0 : dp2[V]);}
}

2. 分割等和子集

. - 力扣（LeetCode）

2.1 算法原理 

  • 问题转化:

将数组分割两个等和的子集 --> 数组是否存在和为 sum / 2 的子集

  • 状态表示:

dp[i][j]: 从前 i 个数中选, 能否凑成 j 这个数

  • 状态转移方程:

选 i --> if(j - nums[i] >= 0) --> dp[i - 1][j - nums[i]]

不选 i --> dp[i - 1][j]

dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j]

  • 初始化:

多开辟一行, 多开辟一列.

1. 下标映射

2. 里面的值要保证后续的填表是正确的 

  • 建表顺序:

从上往下

  • 返回值:

dp[n][sum / 2]

 

2.2 算法代码

class Solution {public boolean canPartition(int[] nums) {// 数组是否存在和为 sum / 2 的子集int n = nums.length;int sum = 0;for(int x : nums) sum += x;if(sum % 2 != 0) return false;boolean[][] dp = new boolean[n + 1][sum / 2 + 1];// 初始化for(int i = 0; i <= n; i++) dp[i][0] = true;// 填表for(int i = 1; i <= n; i++) {for(int j = 1; j <= sum / 2; j++) {dp[i][j] = dp[i - 1][j];if(j - nums[i - 1] >= 0) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];}}return dp[n][sum / 2];}/*** 空间优化* @param nums* @return*/public boolean canPartition1(int[] nums) {// 空间优化版本// 数组是否存在和为 sum / 2 的子集int n = nums.length;int sum = 0;for(int x : nums) sum += x;if(sum % 2 != 0) return false;boolean[] dp = new boolean[sum / 2 + 1];// 初始化dp[0] = true;// 填表for(int i = 1; i <= n; i++) {for(int j = sum / 2; j >= nums[i - 1]; j--) {dp[j] = dp[j] || dp[j - nums[i - 1]];}}return dp[sum / 2];}
}

3. 目标和

. - 力扣（LeetCode）

3.1 算法原理 

  • 问题转化:

从数组中选一些数, 使这些数总和为 a , 一共有多少种选法

  • 状态表示dp[i][j]:

从数组前 i 个位置中选, 使得总和为 j , 一共有多少种选法

  • 状态转移方程:

选 i --> j - nums[i] >= 0 --> dp[i- 1][j - nums[i]]
不选 i --> dp[i - 1][j]

dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j]

  • 建表顺序:

从上往下

  • 返回值:

dp[n][a]

3.2 算法代码

class Solution {public int findTargetSumWays(int[] nums, int target) {int n = nums.length;int sum = 0;for(int x : nums) sum += x;int aim = (sum + target) / 2;if(aim < 0 || (sum + target) % 2 == 1) return 0;int[][] dp = new int[n + 1][aim + 1];dp[0][0] = 1;for(int i = 1; i <= n; i++) {for(int j = 0; j <= aim; j++) {dp[i][j] = dp[i - 1][j];if(j - nums[i - 1] >= 0) dp[i][j] += dp[i - 1][j - nums[i - 1]];}}return dp[n][aim];}/***  空间优化* @param nums* @param target* @return*/public int findTargetSumWays1(int[] nums, int target) {int n = nums.length;int sum = 0;for(int x : nums) sum += x;int aim = (sum + target) / 2;if(aim < 0 || (sum + target) % 2 == 1) return 0;int[] dp = new int[aim + 1];dp[0] = 1;for(int i = 1; i <= n; i++) {for(int j = aim; j >= nums[i - 1]; j--) {dp[j] += dp[j - nums[i - 1]];}}return dp[aim];}
}

4. 最后一块石头的重量 II 

. - 力扣（LeetCode） 

4.1 算法原理 

  • 问题转化:

从数组中选出一些数, 使和最接近 sum / 2 

  • 状态表示dp[i][j]:

从数组的前 i 个位置中选, 总和不超过 j, 此时的最大和

  • 状态转移方程:

选 i --> j - nums[i] >= 0 --> dp[i- 1][j - nums[i]] + nums[i]
不选 i --> dp[i - 1][j]

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])

  • 建表顺序:

从上往下

  • 返回值:

sum - dp[n][sum / 2] * 2

4.2 算法代码

class Solution {public int lastStoneWeightII(int[] stones) {int n = stones.length;int sum = 0;for(int x : stones) sum += x;int[][] dp = new int[n + 1][sum / 2 + 1];for(int i = 1; i <= n; i++) {for(int j = 1; j <= sum / 2; j++) {dp[i][j] = dp[i - 1][j];if(j - stones[i - 1] >= 0) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);}}int ret = sum - dp[n][sum / 2];return Math.abs(ret - dp[n][sum / 2]);}/***  空间优化* @param stones* @return*/public int lastStoneWeightII1(int[] stones) {int n = stones.length;int sum = 0;for(int x : stones) sum += x;int[] dp = new int[sum / 2 + 1];for(int i = 1; i <= n; i++) {for(int j = sum / 2; j >= stones[i - 1]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);}}int ret = sum - dp[sum / 2];return Math.abs(ret - dp[sum / 2]);}
}

END


http://www.mrgr.cn/news/57395.html

相关文章：

  • 十一、pico+Unity交互开发教程——手指触控交互（Poke Interaction）
  • Android 12.0进程保活白名单功能实现
  • 【单元测试】深入解剖单元测试的思维逻辑
  • python程序设计员—练习笔记
  • Leetcode—194. 转置文件【中等】（Shell）
  • 123页满分PPT | 华为流程体系建设与运营
  • 1024是什么日子
  • 头条微头条文章洗稿发布软件注意事项（四）
  • 中国最有钱的起名大师颜廷利名字的含义和历史背景是什么？
  • CF978
  • C++ 判断语句的深入解析
  • 使用亚马逊SQS实现一个队列任务，包括：向队列发送消息和从队列中读取消息
  • IBM Granite 3.0:一款开源，SOTA 企业模型
  • python画图|坐标轴显隐设置
  • 【开源鸿蒙】OpenHarmony 5.0轻量系统最小开发环境搭建
  • AI自主学习：未来的智能系统
  • 近似推断 - 最大后验推断和稀疏编码篇
  • AI学习指南深度学习篇-对比学习的变种
  • Python | Leetcode Python题解之第503题下一个更大元素II
  • SELinux详解
  • Golang | Leetcode Golang题解之第504题七进制数
  • 一文彻底搞透Redis的数据类型及具体的应用场景
  • 重温Java基础语法随笔录
  • 【QT】常用控件（四）
  • 12_Linux进程管理命令详解
  • 使用Dask在多块AMD GPU上加速XGBoost