算法系列--动态规划--背包问题(1)--01背包介绍（上）
https://developer.aliyun.com/article/1480834?spm=a2c6h.13148508.setting.14.5f4e4f0eIqvzeb
💕"趁着年轻,做一些比较cool的事情"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(1)–01背包介绍
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(1)--01背包介绍
状态转移方程
这里多了个限制条件dp[i - 1][j - v[i]] != -1,还是根据题目要求得来的,要考虑一种特殊情况,也就是在[0,i]区间内的物品根本无法组合成体积为j的情况(这也是会存在的),要想i位置存在价值,必须保证i-1位置刚好能够实现j-v[i]的体积
初始化相较于第一问也有所不同,具体来说需要把dp表的第一行初始化为-1(除了dp[0][0]),第一行代表不选择任何物品,也就无法构成满足j体积这个条件,我们将其设置为-1
之所以设置为-1是为了和dp[0][0] = 0这种情况作区分
代码:
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static int N = 1010; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), V = in.nextInt();// 获取物品数目和背包体积 // 处理第一问 int[] v = new int[N],w = new int[N];// 存储物品的体积和价值 for(int i = 1; i <= n; i++) {// 输入数值 v[i] = in.nextInt(); w[i] = in.nextInt(); } int[][] dp = new int[N][N]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; if(j - v[i] >= 0) dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]); } } System.out.println(dp[n][V]); // 处理第二问 dp = new int[N][N]; for(int j = 1; j <= V; j++) {// 初始化 dp[0][j] = -1; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; if(j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]); } } System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]); } }
上述解法的空间复杂度是很高的,我们开辟的dp表是一个N*N的,下面介绍使用滚动数组实现空间优化
空间优化之后的代码:
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static int N = 1010; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), V = in.nextInt();// 获取物品数目和背包体积 // 处理第一问 int[] v = new int[N],w = new int[N];// 存储物品的体积和价值 for(int i = 1; i <= n; i++) {// 输入数值 v[i] = in.nextInt(); w[i] = in.nextInt(); } int[] dp = new int[N]; for(int i = 1; i <= n; i++) for(int j = V; j >= v[i]; j--) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]); System.out.println(dp[V]); // 处理第二问 dp = new int[N]; for(int j = 1; j <= V; j++) dp[j] = -1;// 初始化 for(int i = 1; i <= n; i++) for(int j = V; j >= v[i]; j--) if(j - v[i] >= 0 && dp[j - v[i]] != -1) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]); System.out.println(dp[V] == -1 ? 0 : dp[V]); } }
总结:本文的核心要点
- 什么是背包问题
- 01背包问题详解
- 背包问题的空间优化(滚动数组)
以上就是
算法系列--动态规划--背包问题(1)--01背包介绍全部内容,下一篇文章将会带来01背包问题的拓展题目,敬请期待,我是LvZi
